ปัญหาที่ฟังดูง่ายส่งผลให้ตัวเลขใหญ่เกินไปสำหรับจักรวาลของเรา | นิตยสารควอนต้า

ไม่บ่อยนักที่เด็กอายุ 5 ขวบจะเข้าใจคำถามที่อยู่นอกกรอบวิทยาการคอมพิวเตอร์ แต่ก็สามารถเกิดขึ้นได้ ตัวอย่างเช่น สมมติว่าเด็กอนุบาลชื่ออลิซมีแอปเปิ้ล XNUMX ลูก แต่เธอชอบส้มมากกว่า โชคดีที่เพื่อนร่วมชั้นของเธอได้พัฒนาระบบการซื้อขายผลไม้ที่ดีต่อสุขภาพด้วยอัตราแลกเปลี่ยนที่บังคับใช้อย่างเข้มงวด: เลิกแอปเปิ้ลแล้วพูดแล้วคุณจะได้กล้วย อลิซสามารถดำเนินการค้าขายหลายอย่างโดยเก็บกล้วยหรือแคนตาลูปลงเพื่อพาเธอไปสู่ผลไม้ที่เธอชอบได้หรือไม่?

มันฟังดูง่ายพอ “คุณสามารถไปโรงเรียนประถมและบอกกับเด็กๆ ได้” กล่าว คริสตอฟ ฮาสนักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัยออกซ์ฟอร์ด “ผู้คนจะคิดว่า 'นั่นต้องเป็นเรื่องง่าย'”

แต่ปัญหาทางคณิตศาสตร์ที่เป็นสาเหตุของภาวะที่กลืนไม่เข้าคายไม่ออกของอลิซ ที่เรียกว่าปัญหาความสามารถในการเข้าถึงสำหรับระบบบวกเวกเตอร์ เป็นเรื่องที่ละเอียดอ่อนอย่างน่าประหลาดใจ แม้ว่าบางกรณีจะสามารถแก้ไขได้ง่าย แต่นักวิทยาศาสตร์คอมพิวเตอร์ก็ต่อสู้ดิ้นรนมาเกือบครึ่งศตวรรษเพื่อพัฒนาความเข้าใจที่ครอบคลุมเกี่ยวกับปัญหา ในปัจจุบัน ความก้าวหน้าอย่างต่อเนื่องในช่วงไม่กี่ปีที่ผ่านมา พวกเขาได้กำหนดไว้อย่างชัดเจนว่าปัญหาดังกล่าวจะซับซ้อนเพียงใด

ปรากฎว่าปัญหาแบบเด็กๆ นี้ช่างไร้สาระ เกือบจะซับซ้อนแบบการ์ตูน — ซับซ้อนมากจนแทบจะเป็นอย่างอื่นเลย ปัญหาการคำนวณอันโด่งดัง ดูเหมือนเป็นการเล่นของเด็กนะ พยายามหาปริมาณความพยายามที่จำเป็นในการแก้ปัญหานี้ และในไม่ช้า คุณจะต้องเผชิญกับตัวเลขที่ใหญ่มากจนแม้แต่การนับตัวเลขก็ยังทำให้คุณเข้าถึงตัวเลขที่คุณไม่เคยได้ยินมาก่อน ตัวเลขดังกล่าวมักจะเชิญชวนให้มีการเปรียบเทียบกับขนาดของจักรวาล แต่การเปรียบเทียบเหล่านั้นก็ยังไม่เพียงพอ “นั่นจะไม่ทำให้เกิดความยุติธรรม” กล่าว เกออร์ก เซตซ์เชอนักวิทยาศาสตร์คอมพิวเตอร์ที่ Max Planck Institute for Software Systems ในเมืองไคเซอร์สเลาเทิร์น ประเทศเยอรมนี “จักรวาลมีขนาดเล็กมาก”

ภายในการเข้าถึง?

ปัญหาการเข้าถึงได้นั้นเกี่ยวกับวัตถุทางคณิตศาสตร์ที่เรียกว่าเวกเตอร์ ซึ่งเป็นรายการเรียงลำดับของตัวเลข โดยสรุปแล้ว รายการในรายการเหล่านี้เรียกว่าส่วนประกอบ และจำนวนส่วนประกอบในเวกเตอร์เรียกว่ามิติข้อมูล ตัวอย่างเช่น รายการผลไม้ของอลิซสามารถอธิบายได้ด้วยเวกเตอร์สี่มิติ (a, b, c, d), ซึ่งมีส่วนประกอบเป็นตัวแทนของแอปเปิ้ล กล้วย แคนตาลูป และส้มที่เธอมีในช่วงเวลาหนึ่งๆ

ระบบบวกเวกเตอร์หรือ VAS คือชุดของเวกเตอร์ที่แสดงถึงการเปลี่ยนแปลงที่เป็นไปได้ระหว่างสถานะต่างๆ ในระบบ สำหรับอลิซ เวกเตอร์การเปลี่ยนผ่าน (−1, −1, 1, 0) จะแสดงแทนการแลกเปลี่ยนแอปเปิ้ลและกล้วยเป็นแคนตาลูป ปัญหาความสามารถในการเข้าถึงของ VAS ถามว่ามีการผสมผสานระหว่างการเปลี่ยนที่อนุญาตซึ่งสามารถนำคุณจากสถานะเริ่มต้นที่เฉพาะเจาะจงไปยังสถานะเป้าหมายเฉพาะได้หรือไม่ หรือในแง่คณิตศาสตร์ มีผลรวมของเวกเตอร์การเปลี่ยนแปลงที่แปลงเวกเตอร์เริ่มต้นเป็นเวกเตอร์เป้าหมายหรือไม่ มีเพียงสิ่งเดียวที่จับได้: ไม่มีส่วนประกอบใดของเวกเตอร์ที่อธิบายสถานะของระบบสามารถลดลงต่ำกว่าศูนย์ได้

“นั่นเป็นข้อจำกัดที่เป็นธรรมชาติมากสำหรับแบบจำลองความเป็นจริง” กล่าว วอจเซียค เซอร์วินสกี้นักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยวอร์ซอ “คุณไม่สามารถมีแอปเปิ้ลติดลบได้”

ในบางระบบ เป็นเรื่องง่ายที่จะพิจารณาว่าเวกเตอร์เป้าหมายสามารถเข้าถึงได้หรือไม่ แต่นั่นไม่ใช่กรณีเสมอไป นักวิทยาศาสตร์คอมพิวเตอร์มีความสนใจมากที่สุดในระบบการบวกเวกเตอร์ที่ดูเรียบง่าย ซึ่งไม่ชัดเจนว่าการระบุความสามารถในการเข้าถึงนั้นยากเพียงใด ในการศึกษากรณีเหล่านั้น นักวิจัยเริ่มต้นด้วยการกำหนดตัวเลขที่วัดขนาดของระบบที่กำหนด ตัวเลขนี้แสดงโดย nครอบคลุมจำนวนมิติข้อมูล จำนวนการเปลี่ยน และปัจจัยอื่นๆ จากนั้นพวกเขาถามว่าความยากของปัญหาความสามารถในการเข้าถึงจะเพิ่มขึ้นได้เร็วแค่ไหน n เติบโตขึ้น

เพื่อตอบคำถามดังกล่าว นักวิจัยใช้สองแนวทางเสริม ขั้นแรก พวกเขาค้นหาตัวอย่างของระบบบวกเวกเตอร์ที่ยุ่งยากเป็นพิเศษ ซึ่งการพิจารณาความสามารถในการเข้าถึงต้องใช้ความพยายามขั้นต่ำ ระดับขั้นต่ำเหล่านั้นเรียกว่า "ขอบเขตล่าง" สำหรับความซับซ้อนของปัญหา - พวกเขาพูดกับนักวิจัยว่า "ระบบที่ยุ่งยากที่สุดสำหรับสิ่งหนึ่งๆ n อย่างน้อยก็ยากขนาดนี้”

ประการที่สอง นักวิจัยพยายามสร้าง “ขอบเขตบน” — ขีดจำกัดความสามารถในการเข้าถึงได้ยาก แม้จะอยู่ในระบบที่โหดร้ายที่สุดก็ตาม สิ่งเหล่านี้กล่าวว่า “กรณีที่ยากที่สุดสำหรับสิ่งใดสิ่งหนึ่ง n ยากที่สุดถึงขนาดนี้” เพื่อระบุอย่างแม่นยำว่าการเข้าถึงได้ยากเพียงใดในระบบที่ยากที่สุด นักวิจัยพยายามดันขอบเขตล่างขึ้นและขอบเขตบนลงจนกว่าจะพบกัน

เรื่องของฝันร้าย

ระบบบวกเวกเตอร์มีประวัติอันยาวนาน นับตั้งแต่ทศวรรษ 1960 เป็นต้นมา นักวิทยาศาสตร์คอมพิวเตอร์ได้ใช้สิ่งเหล่านี้เพื่อสร้างแบบจำลองโปรแกรมที่แยกการคำนวณออกเป็นชิ้นเล็กๆ จำนวนมาก และทำงานชิ้นเหล่านั้นไปพร้อมๆ กัน “การคำนวณที่เกิดขึ้นพร้อมกัน” ประเภทนี้แพร่หลายไปแล้ว แต่นักวิจัยยังไม่เข้าใจพื้นฐานทางคณิตศาสตร์ของมันอย่างถ่องแท้

ในปี พ.ศ. 1976 นักวิทยาศาสตร์คอมพิวเตอร์ ริชาร์ด ลิปตัน ก้าวแรกสู่การทำความเข้าใจความซับซ้อนของปัญหาความสามารถในการเข้าถึง VAS เขาได้พัฒนาขั้นตอนสำหรับการสร้างระบบซึ่งวิธีที่เร็วที่สุดในการพิจารณาว่ารัฐหนึ่งสามารถเข้าถึงได้จากอีกรัฐหนึ่งหรือไม่คือการวางแผนลำดับการเปลี่ยนผ่านระหว่างรัฐเหล่านั้น นั่นทำให้เขาสามารถใช้ความยาวของเส้นทางที่สั้นที่สุดระหว่างสองรัฐที่ได้รับการคัดเลือกมาอย่างดีเพื่อเป็นการวัดความยากของปัญหาในการเข้าถึง

ลิปตันแล้ว พิสูจน์แล้วว่า เขาสามารถสร้างระบบขนาดได้ n ซึ่งเส้นทางที่สั้นที่สุดระหว่างสองรัฐเกี่ยวข้องกับการเปลี่ยนผ่านมากกว่า $latex 2^{2^n}$ นั่นหมายถึงขอบเขตล่างแบบเอ็กซ์โพเนนเชียลสองเท่าที่สอดคล้องกันกับความพยายามที่จำเป็นในการกำหนดความสามารถในการเข้าถึงในระบบของเขา เป็นการค้นพบที่น่าตกใจ — การเติบโตแบบทวีคูณสองเท่าถือเป็นฝันร้ายของนักวิทยาศาสตร์คอมพิวเตอร์ แท้จริงแล้ว นักวิจัยมักจะชะงักแม้กระทั่งการเติบโตแบบเอ็กซ์โปเนนเชียลธรรมดา ซึ่งดูซีดเซียวเมื่อเปรียบเทียบ: $latex {2^5}= 32$ แต่ $latex 2^{2^5}$ มีมูลค่ามากกว่า 4 พันล้าน

นักวิจัยส่วนใหญ่คิดว่าลิปตันได้สร้างระบบการบวกเวกเตอร์ที่ซับซ้อนที่สุดเท่าที่จะเป็นไปได้ ซึ่งหมายความว่าเขาได้เพิ่มขอบเขตล่างให้สูงที่สุดเท่าที่จะเป็นไปได้ สิ่งเดียวที่ขาดหายไปในกรณีนี้คือขอบเขตสูงสุดที่จะไปด้วยกัน นั่นคือข้อพิสูจน์ว่าไม่มีระบบใดที่การกำหนดความสามารถในการเข้าถึงจะยากยิ่งกว่านี้ แต่ไม่มีใครรู้วิธีพิสูจน์สิ่งนั้น นักวิทยาศาสตร์คอมพิวเตอร์ Ernst Mayr เข้ามาใกล้ที่สุดเมื่อเขา พิสูจน์แล้วว่า โดยหลักการแล้ว ในปี 1981 เป็นไปได้เสมอที่จะกำหนดความสามารถในการเข้าถึงในระบบการบวกเวกเตอร์ใดๆ แต่การพิสูจน์ของเขาไม่ได้กำหนดขอบเขตบนเชิงปริมาณว่าปัญหาจะยากเพียงใด มีพื้นแต่ไม่เห็นเพดาน

“ฉันคิดถึงเรื่องนี้อย่างแน่นอน” ลิปตันกล่าว “แต่หลังจากนั้นไม่นานฉันก็ยอมแพ้ และเท่าที่ฉันสามารถบอกได้ว่าไม่มีใครก้าวหน้าไปตลอดระยะเวลา 40 ปี”

ในปี 2015 นักวิทยาศาสตร์คอมพิวเตอร์ เจโรม เลอรูซ์ และ ซิลเวน ชมิทซ์ ในที่สุดก็ก่อตั้งขึ้น ขอบเขตบนเชิงปริมาณ — สิ่งหนึ่งที่สูงเสียจนนักวิจัยสันนิษฐานว่ามันเป็นเพียงก้าวแรกที่สามารถผลักลงไปให้ถึงขอบเขตล่างของลิปตันได้

แต่นั่นไม่ใช่สิ่งที่เกิดขึ้น ในปี 2019 นักวิจัยค้นพบขอบเขตล่างที่สูงกว่าของลิปตันอย่างมาก ซึ่งพลิกฟื้นภูมิปัญญาดั้งเดิมที่สืบทอดกันมาหลายทศวรรษ ปัญหาความสามารถในการเข้าถึงของ VAS นั้นซับซ้อนเกินกว่าใครจะคาดคิดไว้มาก

หอคอยแห่งพลัง

ผลลัพธ์ที่น่าตกใจในปี 2019 เกิดขึ้นจากความล้มเหลว ในปี 2018 Czerwiński หักล้างการคาดเดาโดย Leroux และ ฟิลิป มาโซเวียคกีซึ่งเป็นนักวิทยาศาสตร์คอมพิวเตอร์ที่ปัจจุบันอยู่ที่มหาวิทยาลัยวอร์ซอ ซึ่งจะช่วยให้ความคืบหน้าในการแก้ปัญหาที่เกี่ยวข้องได้ ในการอภิปรายครั้งต่อๆ มา นักวิจัยได้ค้นพบแนวทางใหม่ในการสร้างระบบการบวกเวกเตอร์ที่ซับซ้อนเป็นพิเศษ ซึ่งอาจบ่งบอกถึงขอบเขตล่างใหม่ของปัญหาความสามารถในการเข้าถึง VAS ซึ่งความคืบหน้าได้หยุดชะงักลงเป็นเวลานาน

“ทุกอย่างเชื่อมโยงอยู่ในใจฉันกับความสามารถในการเข้าถึง VAS” Czerwiński เล่า ในระหว่างภาคการศึกษาที่มีภาระการสอนไม่มาก เขาตัดสินใจที่จะมุ่งเน้นไปที่ปัญหานั้นโดยเฉพาะ ร่วมกับ Leroux, Mazowiecki และนักวิจัยอีกสองคน — สวาโวมีร์ ลาโซตา ของมหาวิทยาลัยวอร์ซอและ รันโก้ ลาซิช ของมหาวิทยาลัยวอริก

หลังจากนั้นไม่กี่เดือน ความพยายามของพวกเขาก็สัมฤทธิ์ผล Czerwiński และเพื่อนร่วมงานของเขา แสดงให้เห็นถึง ว่าพวกเขาสามารถสร้างระบบการบวกเวกเตอร์ได้ ซึ่งเส้นทางที่สั้นที่สุดระหว่างสองสถานะสัมพันธ์กับขนาดของระบบโดยการดำเนินการทางคณิตศาสตร์ที่เรียกว่า tetration ซึ่งทำให้การเติบโตแบบเลขชี้กำลังสองเท่าที่น่าฝันร้ายนั้นดูเชื่อง

การเทเทรชันคือส่วนขยายที่ตรงไปตรงมาของรูปแบบที่เชื่อมโยงการดำเนินการที่คุ้นเคยที่สุดในคณิตศาสตร์ โดยเริ่มจากการบวก เพิ่มเข้าด้วยกัน n สำเนาของตัวเลข และผลลัพธ์จะเท่ากับการคูณตัวเลขนั้นด้วย n. ถ้าคูณกัน n สำเนาตัวเลขที่เทียบเท่ากับการยกกำลังหรือเพิ่มจำนวนเป็น nพลัง การเตตเตอรีซึ่งมักแสดงด้วยลูกศรคู่หนึ่งชี้ขึ้น เป็นขั้นตอนต่อไปในลำดับนี้: การเตตเตอรีตัวเลขด้วย n หมายถึงการยกกำลังมัน n ครั้งเพื่อสร้างหอคอยแห่งพลัง n เรื่องราวสูง

เป็นเรื่องยากที่จะคาดเดาว่า tetration หมดเร็วแค่ไหน: $latex 2 uparrowuparrow 3$ หรือ $latex 2^{2^2}$ คือ 16, $latex 2 uparrowuparrow 4$ มีมูลค่ามากกว่า 65,000 และ $latex 2 uparrowuparrow 5$ เป็นตัวเลขที่มีจำนวนเกือบ 20,000 หลัก เป็นไปไม่ได้ทางกายภาพที่จะจดตัวเลขทั้งหมดของ $latex 2 uparrowuparrow 6$ ซึ่งเป็นความรับผิดชอบของการมีชีวิตอยู่ในจักรวาลเล็กๆ เช่นนี้

จากผลลัพธ์ที่สำคัญ Czerwiński และเพื่อนร่วมงานของเขาได้พิสูจน์ว่ามีระบบการบวกเวกเตอร์ของขนาด n โดยที่วิธีที่ดีที่สุดในการกำหนดความสามารถในการเข้าถึงคือการกำหนดเส้นทางที่เกี่ยวข้องกับการเปลี่ยนมากกว่า $latex 2 uparrowuparrow n$ ซึ่งหมายถึงขอบเขตล่างใหม่ที่แคบลงของ Lipton แต่ถึงแม้จะเป็นเรื่องที่ชวนปวดหัว แต่ก็ยังไม่ใช่คำตอบสุดท้ายเกี่ยวกับความซับซ้อนของปัญหา

สู่ Quinquagintillion และ Beyond 

เพียงไม่กี่เดือนหลังจากขอบเขตล่างใหม่ที่น่าตกใจเกี่ยวกับความซับซ้อนของการเข้าถึง VAS, Leroux และ Schmitz ผลักลง ขอบเขตบนที่พวกเขาตั้งขึ้นเมื่อสามปีก่อน แต่พวกเขาไม่ได้ลงไปจนถึงการสั่นคลอน แต่พวกเขาได้พิสูจน์ว่าความซับซ้อนของปัญหาความสามารถในการเข้าถึงไม่สามารถเติบโตได้เร็วกว่าความแปลกประหลาดทางคณิตศาสตร์ที่เรียกว่าฟังก์ชันแอคเคอร์มันน์

เพื่อให้เข้าใจถึงหน้าที่นั้น ให้ใช้รูปแบบที่ใช้ในการนิยามความ tetration ไปสู่ข้อสรุปที่น่ากลัว การดำเนินการถัดไปในลำดับ เรียกว่าเพนเทชัน แสดงถึงการเทเทรชันซ้ำๆ ตามมาด้วยการดำเนินการอีกครั้ง (การหกเหลี่ยม) สำหรับการกักขังซ้ำๆ และอื่นๆ

ฟังก์ชัน Ackermann ซึ่งหมายถึง $latex A(n)$ คือสิ่งที่คุณได้รับเมื่อคุณเลื่อนขึ้นบันไดการดำเนินการหนึ่งขั้นโดยแต่ละจุดบนเส้นจำนวน: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 ลูกศรขึ้น 4=4^{4^{4^4}}$ และอื่นๆ จำนวนหลักใน $latex A(4)$ นั้นเป็นจำนวนมหาศาลโดยประมาณเท่ากับ 1 quinquagintillion ซึ่งเป็นชื่อที่แปลกและไม่ค่อยมีใครต้องการสำหรับ 1 ตามด้วยศูนย์ 153 ตัว “อย่ากังวลกับอัคเคอร์มันน์ทั้ง 5 คน” แนะนำ ฮาเวียร์ เอสปาร์ซ่านักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยเทคนิคมิวนิก

ผลลัพธ์ของ Leroux และ Schmitz ทำให้เกิดช่องว่างขนาดใหญ่ระหว่างขอบเขตล่างและบน - ความซับซ้อนที่แม่นยำของปัญหาความสามารถในการเข้าถึง VAS อาจอยู่ที่ปลายด้านใดด้านหนึ่งของช่วงหรือที่ใดก็ได้ในระหว่างนั้น Czerwińskiไม่ได้ตั้งใจที่จะปล่อยให้ช่องว่างนั้นยังคงอยู่ “เราพยายามทำสิ่งนี้ต่อไปเพราะชัดเจนว่านี่คือสิ่งยิ่งใหญ่ที่สุดที่เราเคยทำในชีวิต” เขากล่าว

ความก้าวหน้าครั้งสุดท้ายเกิดขึ้นในปี 2021 ขณะที่ Czerwiński กำลังให้คำปรึกษานักศึกษาระดับปริญญาตรีปีที่สองชื่อ Łukasz Orlikowski เขามอบหมายให้ Orlikowski เป็นรูปแบบง่ายๆ ของปัญหาเพื่อให้เขาเร่งความเร็วขึ้น และงานของ Orlikowski ช่วยให้ทั้งสองคนพัฒนาเทคนิคใหม่ที่นำไปใช้กับปัญหาความสามารถในการเข้าถึงทั่วไปด้วย นั่นทำให้พวกเขาสามารถ ยกขอบเขตล่างขึ้น อย่างมาก — ไปจนถึงขอบเขตบนของ Leroux และ Ackermann ของ Schmitz ทำงานอย่างอิสระ Leroux ได้รับ ผลลัพธ์ที่เทียบเท่า ในเวลาเดียวกัน

ในที่สุด นักวิจัยก็ได้ปักหมุดความซับซ้อนที่แท้จริงของปัญหาความสามารถในการเข้าถึง ขอบล่างของ Czerwiński, Orlikowski และ Leroux แสดงให้เห็นว่ามีลำดับของระบบการบวกเวกเตอร์ที่ใหญ่ขึ้นเรื่อยๆ โดยที่เส้นทางที่สั้นที่สุดระหว่างสองสถานะจะขยายตามสัดส่วนของฟังก์ชันแอคเคอร์มันน์ ขอบเขตสูงสุดของ Leroux และ Schmitz แสดงให้เห็นว่าปัญหาความสามารถในการเข้าถึงไม่สามารถซับซ้อนไปกว่านี้อีกแล้ว — เป็นการปลอบใจเพียงเล็กน้อยสำหรับใครก็ตามที่หวังว่าจะมีขั้นตอนปฏิบัติที่ใช้งานได้จริงในการแก้ไขปัญหานั้นอย่างไม่มีข้อผิดพลาด เป็นภาพประกอบที่ชัดเจนว่าปัญหาทางคอมพิวเตอร์ที่ดูเรียบง่ายนั้นละเอียดอ่อนเพียงใด

ไม่เคยจบ

นักวิจัยยังคงศึกษาปัญหาความสามารถในการเข้าถึง VAS ต่อไปหลังจากระบุความซับซ้อนที่แน่นอนแล้ว เนื่องจากคำถามหลายรูปแบบยังคงไม่ได้รับคำตอบ ตัวอย่างเช่น ขอบเขตบนและล่างของ Ackermann ไม่ได้แยกความแตกต่างระหว่างวิธีเพิ่มขึ้นแบบต่างๆ n, เช่นการเพิ่มมิติของเวกเตอร์หรือการเพิ่มจำนวนการเปลี่ยนที่อนุญาต

ล่าสุด Czerwiński และเพื่อนร่วมงานของเขาได้ มีความคืบหน้า การแยกความแตกต่างระหว่างเอฟเฟกต์ที่แตกต่างเหล่านี้โดยการศึกษาว่าความซับซ้อนสามารถเพิ่มขึ้นได้เร็วแค่ไหนในระบบการบวกเวกเตอร์ที่มีมิติคงที่ แต่ยังต้องดำเนินการอีกมาก แม้จะอยู่ในสามมิติ ซึ่งระบบการเพิ่มเวกเตอร์นั้นง่ายต่อการมองเห็น แต่ยังไม่ทราบความซับซ้อนที่แน่นอนของปัญหาความสามารถในการเข้าถึง

“ในแง่หนึ่ง มันน่าอายสำหรับเรา” Mazowiecki กล่าว

นักวิจัยหวังว่าความเข้าใจที่ดีขึ้นเกี่ยวกับกรณีที่ค่อนข้างง่ายจะช่วยให้พวกเขาพัฒนาเครื่องมือใหม่ๆ เพื่อศึกษาแบบจำลองการคำนวณอื่นๆ ที่ซับซ้อนกว่าระบบการบวกเวกเตอร์ ปัจจุบันเราแทบไม่รู้อะไรเลยเกี่ยวกับโมเดลที่ซับซ้อนกว่านี้เหล่านี้

“ฉันมองว่านี่เป็นส่วนหนึ่งของภารกิจพื้นฐานในการทำความเข้าใจความสามารถในการคำนวณ” Zetzsche กล่าว

ควอนตั้ม กำลังดำเนินการสำรวจชุดต่างๆ เพื่อให้บริการผู้ชมของเราได้ดียิ่งขึ้น เอาของเรา แบบสำรวจผู้อ่านวิทยาการคอมพิวเตอร์ และคุณจะถูกป้อนเพื่อรับรางวัลฟรี ควอนตั้ม สินค้า.