การเดินทาง 50 ปีของทฤษฎีความซับซ้อนสู่ขีดจำกัดของความรู้ | นิตยสารควอนตั้ม

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

“นั่นทำให้ฉันนั่งและให้ความสนใจ” เล่า คาร์โมซิโนซึ่งปัจจุบันเป็นนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีที่ IBM เขาลงทะเบียนเข้าร่วมสัมมนาเสริมเกี่ยวกับงานของ Kurt Gödel ซึ่งข้อโต้แย้งในการอ้างอิงตนเองจนเวียนหัวเผยให้เห็นขีดจำกัดของการให้เหตุผลทางคณิตศาสตร์เป็นครั้งแรก และสร้างรากฐานสำหรับงานในอนาคตทั้งหมดเกี่ยวกับขีดจำกัดพื้นฐานของการคำนวณ มันมีอะไรมากมายที่ต้องเข้ามา

“ฉันไม่เข้าใจ 100%” คาร์โมซิโนกล่าว “แต่ฉันรู้ว่าฉันต้องการ”

ในปัจจุบัน แม้แต่นักวิจัยผู้ช่ำชองยังพบว่ามีความเข้าใจในภาวะขาดแคลนเมื่อพวกเขาเผชิญหน้ากับคำถามเปิดที่สำคัญในวิทยาการคอมพิวเตอร์เชิงทฤษฎี หรือที่เรียกว่าปัญหา P กับ NP โดยพื้นฐานแล้ว คำถามนั้นถามว่าปัญหาทางคอมพิวเตอร์จำนวนมากที่ถือว่ายากมากนั้นสามารถแก้ไขได้ง่ายจริงหรือไม่ (โดยใช้ทางลัดลับที่เรายังไม่ได้ค้นพบ) หรือตามที่นักวิจัยส่วนใหญ่สงสัยว่าปัญหาเหล่านั้นยากจริงๆ หรือไม่ ไม่มีอะไรน้อยไปกว่าธรรมชาติของสิ่งที่รู้ได้

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

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

ดูเหมือนว่าการพิสูจน์ว่าปัญหาทางคอมพิวเตอร์นั้นแก้ไขได้ยากนั้นเป็นงานที่ยาก แต่ทำไมมันยากขนาดนั้นล่ะ? และมันยากแค่ไหน? Carmosino และนักวิจัยคนอื่นๆ ในสาขาย่อยของ meta-complexity ได้กำหนดคำถามใหม่เช่นนี้ว่าเป็นปัญหาทางคอมพิวเตอร์ โดยขับเคลื่อนสนามไปข้างหน้าด้วยการเปลี่ยนเลนส์ของทฤษฎีความซับซ้อนกลับมาที่ตัวมันเอง

“คุณอาจจะคิดว่า 'โอเค มันเจ๋งมาก' บางทีนักทฤษฎีความซับซ้อนอาจคลั่งไคล้ไปแล้ว” กล่าว ราหุล อิลันโกนักศึกษาระดับบัณฑิตศึกษาจาก MIT ที่สร้างผลงานล่าสุดที่น่าตื่นเต้นที่สุดในสาขานี้

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

“เป็นที่ชัดเจนว่าความซับซ้อนของเมตาดาต้านั้นใกล้เคียงกับหัวใจของสิ่งต่าง ๆ” กล่าว สกอตต์ อารอนสันนักทฤษฎีความซับซ้อนแห่งมหาวิทยาลัยเท็กซัส ออสติน

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

ไม่รู้จักไม่รู้จัก

ปัญหา P กับ NP เป็นชื่อที่น่าเบื่อเพราะนิสัยของนักทฤษฎีความซับซ้อนในการแยกแยะปัญหาทางคอมพิวเตอร์ออกเป็นวงกว้าง”คลาสที่ซับซ้อน” โดยมีป้ายกำกับที่บ่งบอกถึงสัญลักษณ์ย่อหุ้น Nasdaq ปัญหาทางการคำนวณคือปัญหาที่โดยหลักการแล้วสามารถแก้ไขได้ด้วยอัลกอริธึม ซึ่งเป็นรายการคำสั่งที่ระบุอย่างแม่นยำ แต่ไม่ใช่ทุกอัลกอริธึมจะมีประโยชน์เท่าเทียมกัน และการแปรผันระหว่างอัลกอริธึมบ่งบอกถึงความแตกต่างพื้นฐานระหว่างปัญหาในคลาสที่ต่างกัน ความท้าทายสำหรับนักทฤษฎีความซับซ้อนคือการเปลี่ยนคำแนะนำเหล่านี้ให้เป็นทฤษฎีบทที่เข้มงวดเกี่ยวกับความสัมพันธ์ระหว่างคลาสของความซับซ้อน

ความสัมพันธ์เหล่านี้สะท้อนถึงความจริงที่ไม่เปลี่ยนแปลงเกี่ยวกับการคำนวณที่ก้าวไปไกลกว่าเทคโนโลยีเฉพาะใดๆ “นี่เหมือนกับการค้นพบกฎของจักรวาล” Kabanets กล่าว

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

ถ้าเป็นเช่นนั้น P = NP: ทั้งสองคลาสมีค่าเท่ากัน หากเป็นเช่นนั้น จะต้องมีอัลกอริธึมบางอย่างที่ทำให้การไขปริศนาซูโดกุขนาดมหึมา เพิ่มประสิทธิภาพเส้นทางการขนส่งทั่วโลก ทำลายการเข้ารหัสที่ล้ำสมัย และทำให้การพิสูจน์ทฤษฎีบททางคณิตศาสตร์เป็นไปโดยอัตโนมัติ ถ้า P ≠ NP ปัญหาทางการคำนวณหลายอย่างที่แก้ไขได้ในหลักการ ในทางปฏิบัติจะคงอยู่นอกเหนือการควบคุมของเราไปตลอดกาล

นักวิจัยกังวลเกี่ยวกับขีดจำกัดของการใช้เหตุผลทางคณิตศาสตร์อย่างเป็นทางการมานานก่อนที่จะมีการพูดถึงปัญหา P กับ NP เป็นครั้งแรก จริงๆ แล้วคือก่อนที่จะเริ่มวิทยาการคอมพิวเตอร์สมัยใหม่เสียอีก ในปี 1921 ด้วยความดิ้นรนกับคำถามเดียวกันที่จะดึงดูดความสนใจของ Carmosino เกือบหนึ่งศตวรรษต่อมา นักคณิตศาสตร์ David Hilbert เสนอโครงการวิจัยเพื่อปูทางคณิตศาสตร์อย่างมั่นใจ เขาหวังว่าจะเริ่มต้นจากสมมติฐานง่ายๆ สองสามข้อที่เรียกว่าสัจพจน์ และได้ทฤษฎีทางคณิตศาสตร์แบบครบวงจรที่ตรงตามเกณฑ์สำคัญสามประการ

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

เพียงหนึ่งปีต่อมา Gödel ได้โจมตีความฝันของฮิลเบิร์ตเป็นครั้งแรก เขา พิสูจน์แล้วว่า ว่าข้อความที่เอาชนะตัวเองเช่น "ข้อความนี้พิสูจน์ไม่ได้" อาจมาจากชุดสัจพจน์ที่เหมาะสม หากข้อความดังกล่าวไม่สามารถพิสูจน์ได้จริง ๆ ทฤษฎีก็จะไม่สมบูรณ์ แต่ถ้าพิสูจน์ได้ ทฤษฎีนั้นก็ไม่สอดคล้องกัน — ผลลัพธ์ที่เลวร้ายยิ่งกว่านั้นอีก ในรายงานฉบับเดียวกัน Gödel ยังพิสูจน์ด้วยว่าไม่มีทฤษฎีทางคณิตศาสตร์ใดที่สามารถพิสูจน์ความสอดคล้องของมันเองได้

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

จากนั้นในปี 1936 นักศึกษาระดับบัณฑิตศึกษาอายุ 23 ปีชื่ออลัน ทัวริงได้ใช้ถ้อยคำเงื่อนไขการตัดสินใจของฮิลเบิร์ตใหม่โดยใช้ภาษาการคำนวณที่ไม่คุ้นเคยในขณะนั้น และจัดการกับปัญหาร้ายแรง ทัวริงได้คิดค้นแบบจำลองทางคณิตศาสตร์ ซึ่งปัจจุบันรู้จักกันในชื่อ เครื่องทัวริง — ซึ่งสามารถแสดงถึงอัลกอริธึมที่เป็นไปได้ทั้งหมด และแสดงให้เห็นว่าหากมีขั้นตอนของฮิลเบิร์ต ขั้นตอนนั้นจะพอดีกับโมเดลนี้ จากนั้นเขาก็ใช้วิธีการอ้างอิงตนเองเช่น Gödel's พิสูจน์ การมีอยู่ของข้อความที่ตัดสินใจไม่ได้ - หรือเทียบเท่ากับปัญหาที่คำนวณไม่ได้ซึ่งอัลกอริทึมไม่สามารถแก้ไขได้

โปรแกรมของฮิลเบิร์ตพังทลายลง: จะมีข้อจำกัดพื้นฐานตลอดไปเกี่ยวกับสิ่งที่สามารถพิสูจน์ได้และสิ่งที่สามารถคำนวณได้ แต่เมื่อคอมพิวเตอร์พัฒนาจากนามธรรมทางทฤษฎีไปสู่เครื่องจักรจริง นักวิจัยก็ตระหนักว่าความแตกต่างง่ายๆ ของทัวริงระหว่างปัญหาที่แก้ไขได้และปัญหาที่แก้ไม่ได้ทำให้เกิดคำถามมากมายที่ยังไม่มีคำตอบ

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

“ทฤษฎีอันมากมายเกิดขึ้น และเราไม่รู้คำตอบอีกต่อไป” คาร์โมซิโนกล่าว

เส้นทางที่แตกต่าง

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

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

มีอัลกอริธึมเส้นทางแฮมิลตันที่ซับซ้อนกว่าซึ่งให้การต่อสู้ที่ดีกว่า แต่เวลาที่อัลกอริธึมต้องใช้ในการแก้ปัญหาจะเพิ่มขึ้นแบบทวีคูณตามขนาดของกราฟอย่างสม่ำเสมอ กราฟไม่จำเป็นต้องมีขนาดใหญ่มาก ก่อนที่นักวิจัยอัลกอริธึมที่เก่งที่สุดจะค้นพบก็ไม่สามารถค้นหาเส้นทางได้ “ในระยะเวลาอันสมควร” กล่าว รัสเซลล์ อิมพากลิอาซโซเป็นนักทฤษฎีเรื่องความซับซ้อนจากมหาวิทยาลัยแคลิฟอร์เนีย ซานดิเอโก “และด้วย 'ระยะเวลาอันสมควร' ฉันหมายถึง 'ก่อนที่จักรวาลจะสิ้นสุด'”

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

เวลาที่ต้องใช้ในการรันอัลกอริธึมการตรวจสอบโซลูชันนี้จะแปรผันตามขนาดของกราฟ นั่นทำให้อัลกอริธึมพหุนามอยู่ในหมวดหมู่ที่กว้างขึ้นของอัลกอริธึมพหุนาม ซึ่งเวลาทำงานเพิ่มขึ้นตามฟังก์ชันพหุนามของขนาดกราฟ การเติบโตพหุนามนั้นเชื่องไม่ได้เมื่อเทียบกับการเติบโตแบบเอ็กซ์โปเนนเชียล ดังนั้นอัลกอริธึมพหุโนเมียลจึงยังคงทำงานได้แม้บนกราฟขนาดใหญ่ “มันมีประสิทธิภาพมากขึ้นอย่างมาก” Carmosino กล่าว

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

สมมติว่าคุณได้รับกราฟอีกครั้ง แต่ตอนนี้คุณถูกขอให้ค้นหา "เส้นทางยูเลอเรียน" ที่ตัดผ่านทุกขอบเพียงครั้งเดียว อีกครั้ง มีอัลกอริธึมพหุนามสำหรับตรวจสอบวิธีแก้ปัญหาที่เป็นไปได้ แต่คราวนี้ยังมีอัลกอริธึมพหุนามสำหรับการแก้ปัญหาด้วย ไม่มีความไม่สมดุลที่นี่ ในทฤษฎีความซับซ้อน บางเส้นทางดูเหมือนจะค้นหาได้ง่ายกว่าเส้นทางอื่นๆ

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

ยากในระดับสากล

ในตอนแรก คลาสความซับซ้อนดูเหมือนเป็นหมวดหมู่ที่สะดวกสำหรับการจัดเรียงปัญหาที่คล้ายกันแต่ไม่เกี่ยวข้องโดยตรง ไม่มีใครสงสัยว่าการค้นหาเส้นทางแฮมิลตันจะเกี่ยวข้องกับปัญหาการคำนวณหนักอื่นๆ

จากนั้นในปี 1971 ภายในหนึ่งปีหลังจากย้ายมาอยู่ที่มหาวิทยาลัยโตรอนโตหลังจากถูกปฏิเสธการดำรงตำแหน่งในสหรัฐอเมริกา นักทฤษฎีความซับซ้อนคนนี้ สตีเฟน คุก ตีพิมพ์ ผลลัพธ์ที่ไม่ธรรมดา. เขาระบุปัญหา NP โดยเฉพาะด้วยคุณลักษณะแปลก ๆ ถ้ามีอัลกอริธึมพหุนามที่สามารถแก้ปัญหานั้นได้ มันก็สามารถแก้ปัญหาอื่น ๆ ใน NP ได้เช่นกัน ดูเหมือนว่าปัญหา “สากล” ของคุกเป็นเพียงคอลัมน์เดียวที่รวบรวมประเภทของปัญหาที่ดูเหมือนจะยาก โดยแยกออกจากปัญหาง่ายๆ ด้านล่างนี้ แก้ไขปัญหานั้นให้หมด แล้ว NP ที่เหลือก็จะพังทลายลง

คุกสงสัยว่าไม่มีอัลกอริธึมที่รวดเร็วสำหรับปัญหาสากลของเขา และเขาก็พูดกลางรายงานโดยเสริมว่า "ฉันรู้สึกว่ามันคุ้มค่าที่จะใช้ความพยายามอย่างมากในการพยายามพิสูจน์การคาดเดานี้" “ความพยายามอย่างมาก” จะกลายเป็นการพูดน้อย

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

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

การแก้ปัญหาความยากของปัญหา NP-complete ใดๆ ก็เพียงพอแล้วที่จะแก้ปัญหาระหว่างคำถาม P กับ NP ถ้า P ≠ NP ความแตกต่างระหว่างปัญหาที่ง่ายและปัญหายากจะคงอยู่ด้วยคอลัมน์หลายพันคอลัมน์ที่ล้วนแข็งแกร่งเท่ากัน หาก P = NP สิ่งปลูกสร้างทั้งหมดกำลังสั่นคลอนจนเกือบจะพังทลาย เพียงรอให้ชิ้นส่วนหนึ่งพังลงมา

คุก เลวิน และคาร์ปได้รวมปัญหาต่างๆ ที่ดูไม่เกี่ยวข้องเข้าด้วยกัน ตอนนี้นักทฤษฎีความซับซ้อนทุกคนต้องทำคือแก้ปัญหาเดียว: P = NP หรือไม่?

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

สมมติว่า P = NP เพื่อพิสูจน์สิ่งนี้ นักวิจัยจะต้องค้นหาอัลกอริธึมที่รวดเร็วสำหรับปัญหา NP-complete ซึ่งอาจซ่อนอยู่ในมุมที่คลุมเครือของภูมิประเทศอันกว้างใหญ่นั้น ไม่มีการรับประกันว่าพวกเขาจะพบมันในเร็วๆ นี้ นักทฤษฎีความซับซ้อนก็มีบ้างเป็นครั้งคราว ค้นพบ อัลกอริธึมอันชาญฉลาดสำหรับปัญหาที่ดูเหมือนยาก (แม้ว่าจะยังไม่สมบูรณ์) หลังจากทำงานมาหลายทศวรรษเท่านั้น

ทีนี้สมมติว่า P ≠ NP การพิสูจน์ว่าดูเหมือนยากยิ่งขึ้น นักทฤษฎีความซับซ้อนจะต้องพิสูจน์ว่าไม่มีอัลกอริธึมที่รวดเร็วใดที่สามารถดำรงอยู่ได้ โดยคาดการณ์และขัดขวางความพยายามที่ดีที่สุดของนักวิจัยในอนาคตทั้งหมดได้อย่างมีประสิทธิภาพ

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

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

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

“เขาแบบว่า 'คุณรู้ไหมว่าถ้าคุณต้องการทำสิ่งนี้ต่อไป หากคุณต้องการทำวิทยาการคอมพิวเตอร์เชิงทฤษฎีและทฤษฎีความซับซ้อนต่อไป คุณก็ทำได้ มันเรียกว่าบัณฑิตวิทยาลัย'” Carmosino กล่าว หลังจากสำเร็จการศึกษาระดับปริญญาโท เขาก็ย้ายไปซานดิเอโกในปี 2012 เพื่อทำงานในระดับปริญญาเอกภายใต้การดูแลของ Impagliazzo

เป้าหมายหลักของ Carmosino ในตอนแรกคือการทำความเข้าใจ a ให้ดีขึ้น กระดาษจุดสังเกต เมื่อสองทศวรรษก่อนหน้านี้ที่ครอบงำจินตนาการของเขา บทความนั้นโดยนักทฤษฎีความซับซ้อน อเล็กซานเดอร์ ราซโบรอฟ และ สตีเว่น รูดิชได้แสดงให้เห็นว่ากลยุทธ์ "ธรรมชาติ" บางอย่างในการพิสูจน์ P ≠ NP เกือบจะล้มเหลวอย่างแน่นอน เพราะความสำเร็จนั้นต้องแลกมาด้วยต้นทุนที่สูงลิ่ว ซึ่งเป็นการพังทลายของการเข้ารหัสโดยสมบูรณ์ ซึ่งนักวิจัยมองว่าไม่น่าเป็นไปได้อย่างยิ่ง นักวิจัยตีความผลลัพธ์ของ Razborov และ Rudich ว่าเป็นอุปสรรคต่อแนวทางยอดนิยมในการพิสูจน์ P ≠ NP

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

“ทฤษฎีความซับซ้อนนั้นถูกสาปและมีอุปสรรคมากมาย” Ilango กล่าว

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

แต่เพื่อติดตามเส้นทางจากอุปสรรคในการพิสูจน์ตามธรรมชาติ ไปสู่ความซับซ้อนของเมตาดาต้า เราจะต้องย้อนกลับไปที่จุดที่เราทิ้งนักวิจัยไว้ในปี 1970 เมื่อพวกเขาเริ่มจัดการกับปัญหา P กับ NP เป็นครั้งแรก อะไรทำให้การพิสูจน์ปัญหาเป็นเรื่องยากมาก?

เส้นทางวงจร

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

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

ในนิพจน์เหล่านี้ ตัวแปรบูลีนจะถูกเชื่อมโยงเข้าด้วยกันโดย "ลอจิกเกต" AND, OR และ NOT ตัวอย่างเช่น นิพจน์พื้นฐาน A และ B เป็นจริงเมื่อทั้ง A และ B เป็นจริง มิฉะนั้นจะเป็นเท็จ ในทางกลับกัน A หรือ B เป็นจริงหากอย่างน้อยหนึ่งในสองตัวแปรเป็นจริง NOT gate นั้นง่ายกว่า: มันจะกลับค่าของตัวแปรตัวเดียว ด้วยองค์ประกอบพื้นฐานเหล่านี้ที่เพียงพอ คุณสามารถทำการคำนวณใดๆ ก็ได้

“เมื่อคุณดูคอมพิวเตอร์ของคุณ ท้ายที่สุดแล้ว มันกำลังทำอะไรอยู่? มันกำลังวิ่งอยู่ในวงจร” Ilango กล่าว

งานของแชนนอนเสนอแนวทางใหม่สำหรับนักทฤษฎีในการคิดถึงความยากของปัญหาทางคอมพิวเตอร์ ที่เรียกว่า "ความซับซ้อนของวงจร" แม้ว่าวงจรที่เป็นปัญหาจะเป็นเพียงนามธรรมทางคณิตศาสตร์ก็ตาม นักวิจัยคิดว่าแนวทางนี้อาจเป็นวิธีการแก้ปัญหา P กับ NP ได้สักระยะหนึ่ง แต่ในที่สุดเส้นทางก็วิ่งไปชนกับสิ่งกีดขวางการพิสูจน์ตามธรรมชาติ

กรอบงานความซับซ้อนของวงจรจำเป็นต้องคิดใหม่เกี่ยวกับแนวคิดพื้นฐานที่สุดในแบบจำลองการคำนวณของทัวริง ที่นี่ แทนที่จะพิจารณาปัญหาทางคอมพิวเตอร์และอัลกอริธึมที่ช่วยแก้ปัญหาเหล่านี้ นักวิจัยพิจารณาฟังก์ชันบูลีนและวงจรที่คำนวณพวกมัน ฟังก์ชันบูลีนรับตัวแปรบูลีน — จริงและเท็จ 1 วินาทีและ 0 — และเอาต์พุตเป็นจริงหรือเท็จ 1 หรือ 0 และเช่นเดียวกับอัลกอริทึม วงจรจะอธิบายขั้นตอนในการสร้างเอาต์พุตเมื่อมีอินพุตใดๆ ก็ตาม

“ความเข้าใจของฉันคือผู้คนเริ่มทำงานกับความซับซ้อนของวงจรเพราะพวกเขาตัดสินใจว่าเครื่องจักรทัวริงซับซ้อนเกินไป” กล่าว ไรอันวิลเลียมส์นักทฤษฎีความซับซ้อนของ MIT “เราสามารถศึกษาวงจรแบบทีละประตูได้”

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

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

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

นี่เป็นกลยุทธ์ที่นักทฤษฎีความซับซ้อนส่วนใหญ่ดำเนินการในช่วงทศวรรษ 1980 และโอกาสก็เข้าข้างพวกเขา แชนนอนก็มี พิสูจน์แล้วว่า ในปี 1949 ตารางความจริงบูลีนเกือบทุกตาราง (ซึ่งเป็นเพียงรายการยาวๆ ของอินพุตและเอาต์พุตที่เป็นไปได้ทั้งหมดของฟังก์ชันบูลีนในขนาดคงที่) มีความซับซ้อนของวงจรที่สูงที่สุดเท่าที่จะเป็นไปได้ เขาใช้ข้อโต้แย้งที่เรียบง่ายอย่างน่าทึ่ง: มีวิธีรวมประตูจำนวนน้อยได้น้อยกว่าวิธีรวมประตูหลาย ๆ อันมาก

“มีวงจรเล็กๆ ไม่เพียงพอที่จะสำรวจ” แอรอนสันกล่าว

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

Crypto Bros

ในตอนแรกความก้าวหน้าเป็นไปอย่างรวดเร็ว ในปี 1981 Sipser และผู้ร่วมงานสองคน พิสูจน์แล้วว่า ฟังก์ชันบูลีนบางอย่างนั้นคำนวณได้ยากอย่างแน่นอนหากใช้วงจรที่มีข้อจำกัดบางประการเกี่ยวกับวิธีการจัดเรียงเกต

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

ในปี 1985 Razborov ก้าวไปอีกขั้นหนึ่ง เขาเพิ่งเริ่มเรียนในระดับบัณฑิตศึกษาในมอสโกวและเข้าร่วมความพยายามโดยไม่ได้ตั้งใจขณะกำลังแก้ไขปัญหาในสาขาวิชาคณิตศาสตร์อื่น ซึ่งปรากฏว่าการแก้ปัญหาระหว่าง P กับ NP นั้นเป็นข้อกำหนดเบื้องต้น

“ฉันโชคดีมากที่ไม่รู้ว่าปัญหานี้ยากแค่ไหน” Razborov กล่าว “ไม่อย่างนั้นฉันคงไม่ได้เริ่มเลย”

Razborov วิเคราะห์วงจรที่มีเกต AND และ OR เท่านั้น และ พิสูจน์แล้วว่า ว่าฟังก์ชันใดฟังก์ชันหนึ่งนั้นคำนวณได้ยากโดยใช้วงจรดังกล่าว ไม่ว่าจะจัดเรียงเกตอย่างไร ยิ่งกว่านั้น ฟังก์ชันนั้นยังเป็นที่รู้จักกันในนาม NP-สมบูรณ์ นักวิจัยทุกคนต้องทำเพื่อแก้ไข P กับ NP โดยขยายเทคนิคของ Razborov ไปยังวงจรที่ไม่มีเกท

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

ในสหรัฐอเมริกา รูดิชกำลังไตร่ตรองคำถามเดียวกันนี้ เขาและ Impagliazzo เป็นเพื่อนร่วมชั้นในวิทยาลัยที่เรียนต่อในระดับบัณฑิตวิทยาลัยด้วยกัน มิตรภาพของพวกเขาถูกจุดประกายด้วยความหลงใหลร่วมกันกับข้อพิสูจน์การอ้างอิงตนเองของ Gödel และ Turing และผลกระทบที่มีต่อรากฐานของคณิตศาสตร์และวิทยาการคอมพิวเตอร์

“เรื่องตลกของเราคือเรากำลังจะได้รับปุ่มที่เขียนว่า 'อ้างอิงตัวเอง'” Impagliazzo กล่าว

ในฐานะนักศึกษาระดับบัณฑิตศึกษา ทั้ง Rudich และ Impagliazzo ต่างก็ทำงานเกี่ยวกับรากฐานทางทฤษฎีที่ซับซ้อนของการเข้ารหัส ซึ่งเป็นวิชาที่อาจเป็นแรงจูงใจในทางปฏิบัติที่ดีที่สุดสำหรับการพยายามพิสูจน์ P ≠ NP นักเข้ารหัสลับปกปิดข้อความลับโดยปิดบังข้อความเหล่านั้นใน "การสุ่มเทียม" ข้อความที่เข้ารหัสด้วยวิธีนี้จะดูเหมือนตัวเลขที่สุ่มสับสนสำหรับผู้ดักฟัง แต่ผู้รับยังสามารถถอดรหัสได้ แต่คุณจะแน่ใจได้อย่างไรว่าผู้แอบฟังจะพบว่าการถอดรหัสนั้นยากเกินไป

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

แม้ว่าวิทยาการเข้ารหัสลับจะน่าหลงใหลในตัวมันเอง แต่วิทยาการเข้ารหัสลับก็ดูห่างไกลจากข้อโต้แย้งในการอ้างอิงตนเองซึ่งดึง Rudich และ Impagliazzo เข้ามาในวงการนี้เป็นครั้งแรก แต่เมื่อ Rudich พยายามทำความเข้าใจว่าทำไมแนวทางความซับซ้อนของวงจรจึงหยุดชะงัก เขาเริ่มตระหนักว่าทั้งสองวิชาไม่ได้ห่างกันมากนัก นักวิจัยด้านกลยุทธ์ได้นำมาใช้ในความพยายามที่จะพิสูจน์ว่า P ≠ NP มีตัวละครที่เอาชนะตัวเองได้ ซึ่งชวนให้นึกถึงข้อเสนอที่มีชื่อเสียงของ Gödel ว่า "ข้อความนี้พิสูจน์ไม่ได้" - และการเข้ารหัสสามารถช่วยอธิบายได้ว่าทำไม ในรัสเซีย Razborov ค้นพบความเชื่อมโยงที่คล้ายกันในเวลาเดียวกัน สิ่งเหล่านี้คือเมล็ดพันธุ์ของกำแพงพิสูจน์ธรรมชาติ

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

เรื่องตลกที่โหดร้าย

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

Sipser, Razborov และคนอื่นๆ ใช้กลยุทธ์เดียวกันนี้อย่างประสบความสำเร็จเพื่อพิสูจน์ผลลัพธ์ที่จำกัดยิ่งขึ้น และในทุกกรณี คุณสมบัติพิเศษที่นักวิจัยระบุนั้นถูกใช้ร่วมกันโดยฟังก์ชันบูลีนส่วนใหญ่ Razborov และ Rudich บัญญัติคำว่า "หลักฐานทางธรรมชาติ" เพื่ออ้างถึงกรณีนี้ซึ่งมีการแบ่งปันทรัพย์สินอย่างกว้างขวาง เพียงเพราะไม่มีทางเลือกอื่นที่ทราบ หากเป็นไปได้ การพิสูจน์ที่ “ผิดธรรมชาติ” จะต้องขัดแย้งกับสัญชาตญาณอย่างมากและสมควรได้รับชื่อดังกล่าว

จากนั้น Razborov และ Rudich ได้พิสูจน์ผลลัพธ์หลักของพวกเขา: การพิสูจน์โดยธรรมชาติของ P ≠ NP จะต้องมีความเข้าใจที่ครอบคลุมอย่างมากว่าฟังก์ชันที่คำนวณง่ายและยากต่อการคำนวณแตกต่างกันอย่างไร และความรู้นั้นยังสามารถกระตุ้นอัลกอริธึมที่รวดเร็วสำหรับการจำแนกได้ง่าย -เพื่อคำนวณฟังก์ชันแม้ว่าจะซับซ้อนเพียงผิวเผินก็ตาม หากนักทฤษฎีความซับซ้อนประสบความสำเร็จในการพิสูจน์ตามธรรมชาติของ P ≠ NP พวกเขาคงจะค้นพบวิธีที่เกือบจะไม่มีข้อผิดพลาดในการดูตารางความจริงตามอำเภอใจและตัดสินว่าฟังก์ชันที่เกี่ยวข้องนั้นมีความซับซ้อนของวงจรสูงหรือต่ำ ซึ่งเป็นผลลัพธ์ที่แข็งแกร่งกว่ามากและเป็นภาพรวมมากกว่า พวกเขาตั้งใจจะพิสูจน์

“คุณแทบจะอดไม่ได้ที่จะได้มากกว่าที่คุณต่อรองไว้” Carmosino กล่าว

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

เพื่อให้เข้าใจถึงการเชื่อมต่อนี้ ลองจินตนาการถึงการดูคอลัมน์เอาต์พุตในตารางความจริงของฟังก์ชันบูลีนที่มีตัวแปรอินพุตจำนวนมาก และแทนที่ "จริง" ทุกรายการด้วย 1 และแทนที่ "เท็จ" ทุกรายการด้วย 0:

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

ดังนั้นผลลัพธ์ของ Razborov และ Rudich แสดงให้เห็นว่าการพิสูจน์ตามธรรมชาติของ P ≠ NP จะให้ผลลัพธ์อัลกอริธึมที่รวดเร็วซึ่งสามารถแยกแยะสตริงสุ่มเทียมที่มีข้อความที่ซ่อนอยู่จากข้อความที่สุ่มอย่างแท้จริง การเข้ารหัสที่ปลอดภัยคงเป็นไปไม่ได้ — ตรงกันข้ามกับสิ่งที่นักวิจัยหวังจะสร้างโดยการพิสูจน์ P ≠ NP อย่างแน่นอน

ในทางกลับกัน หากการเข้ารหัสที่ปลอดภัยเป็นไปได้ การพิสูจน์ตามธรรมชาติก็ไม่ใช่กลยุทธ์ที่ใช้ได้ในการพิสูจน์ P ≠ NP ซึ่งเป็นข้อกำหนดเบื้องต้นสำหรับการเข้ารหัสที่ปลอดภัย นั่นคืออุปสรรคในการพิสูจน์ตามธรรมชาติโดยสรุป ดูเหมือนกับว่านักทฤษฎีความซับซ้อนกำลังตกเป็นเหยื่อของเรื่องตลกอันโหดร้าย

“ถ้าคุณเชื่อในความแข็ง คุณควรเชื่อว่ามันยากที่จะพิสูจน์ความแข็ง” Kabanets กล่าว

เข้าสู่ Metaverse

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

“มีสัญชาตญาณว่า 'โอ้ เพราะ P ≠ NP จึงเป็นเรื่องยากที่จะพิสูจน์ว่า P ≠ NP'” วิลเลียมส์กล่าว “แต่เพื่อที่จะเข้าใจสัญชาตญาณนี้ คุณต้องเริ่มคิดถึงงานพิสูจน์บางอย่างเช่น P ≠ NP ว่าเป็นปัญหาทางคอมพิวเตอร์”

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

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

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

บทความของ Kabanets และ Cai เน้นย้ำถึงปัญหาทางการคำนวณโดยนัยในการกำหนดอุปสรรคในการพิสูจน์ตามธรรมชาติของ Razborov และ Rudich: เมื่อพิจารณาจากตารางความจริงของฟังก์ชันบูลีน ให้พิจารณาว่ามีความซับซ้อนของวงจรสูงหรือต่ำ พวกเขาเรียกสิ่งนี้ว่าปัญหาขนาดวงจรขั้นต่ำหรือ MCSP

MCSP เป็นปัญหาเมตาที่ซับซ้อนที่สำคัญ: ปัญหาการคำนวณที่ไม่ใช่ทฤษฎีกราฟหรือหัวข้อภายนอกอื่น แต่เป็นทฤษฎีความซับซ้อนเอง อันที่จริง มันเหมือนกับคำถามเชิงปริมาณที่ผลักดันให้นักทฤษฎีความซับซ้อนจัดการกับ P กับ NP โดยใช้แนวทางความซับซ้อนของวงจรในทศวรรษ 1980: ฟังก์ชันบูลีนใดที่คำนวณยาก และฟังก์ชันใดที่ง่าย

“ถ้าเราคิดอัลกอริธึม MCSP นั่นก็เหมือนกับวิธีการทำให้สิ่งที่เรากำลังทำในทฤษฎีความซับซ้อนเป็นแบบอัตโนมัติ” Impagliazzo กล่าว “อย่างน้อยก็ควรให้ข้อมูลเชิงลึกอย่างมากแก่เราเกี่ยวกับวิธีการทำงานของเราให้ดีขึ้น”

นักทฤษฎีความซับซ้อนไม่ต้องกังวลว่าอัลกอริธึมมหัศจรรย์นี้จะทำให้พวกมันต้องตกงาน พวกเขาไม่คิดว่ามันจะมีอยู่เลย เพราะ Razborov และ Rudich แสดงให้เห็นว่าอัลกอริทึมใดๆ ก็ตามสำหรับแยกแยะตารางความจริงที่มีความซับซ้อนสูงจากตารางความจริงที่มีความซับซ้อนต่ำจะทำให้การเข้ารหัส เป็นไปไม่ได้. นั่นหมายความว่า MCSP น่าจะเป็นปัญหาด้านการคำนวณที่ยาก แต่มันยากแค่ไหน? มันเป็น NP-complete หรือไม่ เช่น ปัญหาเส้นทางแฮมิลตัน และปัญหาอื่นๆ เกือบทั้งหมดที่นักวิจัยต้องเผชิญในทศวรรษ 1960

สำหรับปัญหาใน NP “ยากแค่ไหน?” มักจะตอบง่ายพอที่จะตอบ แต่ MCSP ดูเหมือนจะเป็นค่าผิดปกติที่แปลก “เรามีปัญหา 'ลอยไปรอบๆ' น้อยมากซึ่งไม่ได้เชื่อมโยงกับปัญหา NP-complete บนเกาะแห่งนี้ แม้ว่าจะดูเหมือนยากก็ตาม” Kabanets กล่าว

Kabanets รู้ว่าเขาและ Cai ไม่ใช่คนแรกที่พิจารณาปัญหาที่พวกเขาเรียกว่า MCSP นักคณิตศาสตร์ชาวโซเวียตได้ศึกษาปัญหาที่คล้ายกันมากเริ่มต้นในทศวรรษปี 1950 โดยเป็นความพยายามในช่วงแรกๆ ที่จะเข้าใจความยากที่แท้จริงของปัญหาการคำนวณต่างๆ Leonid Levin ปล้ำกับมันในขณะที่พัฒนาสิ่งที่จะกลายเป็นทฤษฎีของ NP-ความสมบูรณ์ในช่วงปลายทศวรรษ 1960 แต่เขาไม่สามารถพิสูจน์ได้ว่า NP-สมบูรณ์ และเขาได้ตีพิมพ์รายงานน้ำเชื้อของเขาโดยไม่มีมัน

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

“ในแง่หนึ่ง มันเป็นความซับซ้อนของ meta-meta” กล่าว ราหุลสันธานัม, นักทฤษฎีความซับซ้อนแห่งมหาวิทยาลัยออกซ์ฟอร์ด

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

อาจเป็นไปได้ด้วยว่า MCSP ไม่สมบูรณ์ NP แต่ดูเหมือนว่าจะไม่น่าเป็นไปได้เช่นกัน - ตัวแปรที่ง่ายกว่าบางอย่างของปัญหาเป็นที่ทราบกันดีอยู่แล้วว่าเป็น NP-สมบูรณ์

“เราไม่มีที่ที่ดีที่จะกล่าวถึงมันซึ่งเกี่ยวข้องโดยตรงกับปัญหาอื่น ๆ ทั้งหมดที่เราศึกษา” Impagliazzo กล่าว

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

สงครามแห่งสากลโลก

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

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

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

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

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

เลวินอพยพไปอยู่ที่สหรัฐอเมริกาในปี พ.ศ. 1978 และในช่วงกลางทศวรรษ 1980 เขาได้หันความสนใจไปที่ความซับซ้อนของคดีโดยเฉลี่ย เขาเริ่มทำงานร่วมกับคนอื่นๆ เพื่อพัฒนาทฤษฎีนี้ต่อไป รวมถึง Impagliazzo ซึ่งเป็นนักศึกษาระดับบัณฑิตศึกษาในขณะนั้น แต่แม้ว่าพวกเขาจะก้าวหน้าไป Impagliazzo ก็พบว่านักวิจัยมักจะพูดคุยผ่านกัน เขาต้องการให้ทุกคนเข้าใจตรงกัน และมันไม่ได้ช่วยอะไรเลยที่บทความของเลวินจะมีความกระชับอันโด่งดัง — ฉบับที่ เป็นผู้ริเริ่มภาคสนาม ความซับซ้อนของตัวพิมพ์โดยเฉลี่ยมีความยาวน้อยกว่าสองหน้า

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

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

นับตั้งแต่รายงานของ Impagliazzo ปรากฏขึ้น นักวิจัยต่างใฝ่ฝันที่จะกำจัดบางส่วนของลิขสิทธิ์ขนาดย่อของเขาออกไป — เพื่อจำกัดขอบเขตความเป็นไปได้ด้วยการพิสูจน์ว่าโลกบางใบไม่สามารถทำได้ในที่สุด โลกทั้งสองเป็นเป้าหมายที่น่าดึงดูดเป็นพิเศษ: โลกที่การเข้ารหัสเป็นไปไม่ได้แม้ว่า P ≠ NP ก็ตาม

ในโลกใดโลกหนึ่งที่เรียกว่า Heuristica ปัญหา NP-complete ทั้งหมดนั้นง่ายต่อการแก้ไขด้วยอินพุตส่วนใหญ่ แต่อัลกอริธึมที่รวดเร็วบางครั้งก็ทำให้เกิดข้อผิดพลาด ดังนั้นปัญหาเหล่านี้ยังถือว่ายากตามมาตรฐานของทฤษฎีความซับซ้อนกรณีที่แย่ที่สุด นี่คือโลกที่การเข้ารหัสเป็นไปไม่ได้ เพราะเกือบทุกโค้ดสามารถถอดรหัสได้ง่าย ในอีกโลกหนึ่งที่เรียกว่า Pessiland การเข้ารหัสเป็นไปไม่ได้ด้วยเหตุผลที่แตกต่างกัน: ทุกปัญหานั้นยากในกรณีทั่วไป แต่การเข้ารหัสข้อความทำให้อ่านไม่ออกแม้แต่กับผู้รับที่ต้องการก็ตาม

โลกทั้งสองนี้มีความเชื่อมโยงอย่างใกล้ชิดกับปัญหาความซับซ้อนของเมตาดาต้า โดยเฉพาะอย่างยิ่ง ชะตากรรมของ Heuristica เชื่อมโยงกับคำถามที่มีมายาวนานว่า MCSP นั้นเป็น NP-complete หรือไม่ คำถามที่ทำให้ Kabanets หลงใหลและทำให้ Levin นิ่งงันเมื่อนานมาแล้วไม่ได้เป็นเพียงความอยากรู้อยากเห็น: มีทั้งโลกตกอยู่ในความเสี่ยง

เพื่อแยกแยะ Heuristica นักวิจัยจะต้องยุบความแตกต่างระหว่างความซับซ้อนของกรณีที่แย่ที่สุดและความซับซ้อนของกรณีโดยเฉลี่ย นั่นคือ พวกเขาจะต้องพิสูจน์ว่าอัลกอริทึมสมมุติใดๆ ที่สามารถแก้ปัญหา NP-complete ได้อย่างถูกต้องบนอินพุตส่วนใหญ่สามารถแก้ไขได้จริง ในทุกกรณี. การเชื่อมต่อประเภทนี้เรียกว่ากรณีที่แย่ที่สุดถึงการลดขนาดตัวพิมพ์โดยเฉลี่ย เป็นที่ทราบกันว่ามีอยู่สำหรับปัญหาบางอย่าง แต่ไม่มีปัญหาใดที่ NP สมบูรณ์ ดังนั้นผลลัพธ์เหล่านั้นจึงไม่มีความหมายที่กว้างกว่านั้น การกำจัด Heuristica จะทำให้นักเข้ารหัสใช้เวลาครึ่งทางในการตระหนักถึงความฝันของการเข้ารหัสที่ปลอดภัย โดยอิงตามสมมติฐานเดียวที่ว่า P ≠ NP

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

นักวิจัยจะต้องค้นหาแนวทางอื่น และตอนนี้พวกเขาคิดว่า MCSP อาจเป็นเพียงปัญหาที่พวกเขาต้องการ แต่นั่นจะไม่ชัดเจนมานานกว่าทศวรรษ ภาพแรกของการเชื่อมโยงเกิดขึ้นจากความหลงใหลอย่างไม่ลดละของ Marco Carmosino ที่มีต่อสิ่งกีดขวางตามธรรมชาติ

Carmosino พบกับการวิจัยเมตาที่ซับซ้อนเป็นครั้งแรกในฐานะนักศึกษาระดับบัณฑิตศึกษาผ่านทาง กระดาษ 2013 โดย Kabanets และนักวิจัยอีกสี่คน ซึ่งได้พัฒนาแนวทางในการพิสูจน์อุปสรรคทางธรรมชาติที่ Kabanets ได้บุกเบิกเมื่อกว่าทศวรรษก่อนหน้านี้ มันเพียงแต่เสริมความเชื่อมั่นของเขาว่ายังมีอะไรให้เรียนรู้อีกมากจากรายงานคลาสสิกของ Razborov และ Rudich

“ตอนนั้นฉันหมกมุ่นอยู่กับกระดาษแผ่นนั้น” คาร์โมซิโนกล่าว "ไม่มีอะไรเปลี่ยนแปลง."

ในที่สุดความหลงใหลนี้ก็เกิดผลในระหว่างการเยี่ยมชมเวิร์คช็อประยะยาวภาคเรียนที่ University of California, Berkeley ซึ่งเขาใช้เวลาส่วนใหญ่พูดคุยกับ Impagliazzo, Kabanets และ อันโตนินา โคโลโคโลวานักทฤษฎีความซับซ้อนที่ Memorial University of Newfoundland ซึ่งเคยร่วมงานกับ Kabanets ในรายงานปี 2013 Carmosino เคยร่วมงานกับพวกเขาทั้งสามมาก่อน และการทำงานร่วมกันที่ประสบความสำเร็จนั้นทำให้เขามั่นใจที่จะตอบคำถามเกี่ยวกับหัวข้อที่ทำให้เขาหลงใหลมากที่สุด

“เขาก่อกวนผู้คนในทางที่ดี” Kabanets เล่า

ในตอนแรก คาร์โมซิโนมีแนวคิดใหม่ในการพิสูจน์ความสมบูรณ์ของ NP สำหรับเวอร์ชันของ MCSP ที่ปรากฏในรายงานของ Razborov และ Rudich เกี่ยวกับแผงกั้นการพิสูจน์ตามธรรมชาติ แต่ความคิดเหล่านั้นก็ไม่หลุดออกไป ในทางกลับกัน คำพูดนอกกรอบของ Impagliazzo ทำให้นักวิจัยทั้งสี่คนตระหนักว่าอุปสรรคในการพิสูจน์ตามธรรมชาติสามารถให้อัลกอริธึมที่ทรงพลังมากกว่าที่ใครจะรู้ได้ - มีแผนที่ลับฝังอยู่ในสิ่งกีดขวางบนถนน

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

“ไม่ชัดเจนว่าความเชื่อมโยงดังกล่าวจะเกิดขึ้นได้เลย” Impagliazzo กล่าว

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

แต่สำหรับ MCSP บางเวอร์ชันที่เรียบง่ายกว่า — การแยกแยะตารางความจริงที่มีความซับซ้อนสูงจากตารางความจริงที่มีความซับซ้อนต่ำเมื่อมีข้อจำกัดเฉพาะในวงจร — อัลกอริธึมที่รวดเร็วเป็นที่รู้จักกันมานานหลายปี บทความของ Carmosino, Impagliazzo, Kabanets และ Kolokolova แสดงให้เห็นว่าอัลกอริธึมเหล่านี้สามารถเปลี่ยนเป็นอัลกอริธึมการเรียนรู้ที่ถูกจำกัดเช่นเดียวกันแต่ยังคงทรงพลังมากกว่าที่นักวิจัยเคยเข้าใจมาก่อนในระดับทฤษฎีที่เข้มงวดเช่นนี้

“รสชาติการอ้างอิงตนเองของมันช่วยให้คุณทำสิ่งที่ดูเหมือนว่าคุณไม่สามารถทำได้กับปัญหามาตรฐานมากกว่านี้” Ilango กล่าว

ผลลัพธ์ดังกล่าวดึงดูดความสนใจของนักทฤษฎีความซับซ้อนที่ทำงานในหัวข้ออื่นๆ นอกจากนี้ยังเป็นตัวอย่างของความเชื่อมโยงเพิ่มเติมระหว่างความซับซ้อนของเมตาดาต้าและความซับซ้อนของกรณีโดยเฉลี่ยที่จะเกิดขึ้นในช่วงหลายปีข้างหน้า

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

“ความเป็นคู่แบบนี้เป็นประเด็นสำคัญตลอดช่วง 30 หรือ 40 ปีที่ผ่านมาของความซับซ้อนเป็นอย่างน้อย” Impagliazzo กล่าว “อุปสรรคมักเป็นโอกาส”

เครดิตบางส่วน

ความก้าวหน้าได้เร่งตัวขึ้นในช่วงหลายปีที่ผ่านมานับตั้งแต่ Carmosino และเพื่อนร่วมงานของเขาตีพิมพ์รายงานของพวกเขา

“สิ่งใหม่กำลังเกิดขึ้น” Kolokolova กล่าว “มีนักวิจัยรุ่นเยาว์ที่ฉลาดจริงๆ จำนวนมาก”

Ilango เป็นหนึ่งในนักวิจัยรุ่นเยาว์เหล่านี้ ในช่วงสามปีแรกของการเรียนระดับบัณฑิตศึกษา เขาได้โจมตีปัญหาเปิดที่น่ากังวลในการพิสูจน์ MCSP NP-complete โดยใช้กลยุทธ์แบบสองง่าม: การพิสูจน์ความสมบูรณ์ของ NP สำหรับ ที่เรียบง่าย รุ่น ของ MCSP ดังที่นักวิจัยความซับซ้อนของวงจรทำเมื่อโจมตี P กับ NP ในทศวรรษ 1980 ในขณะเดียวกันก็พิสูจน์ความสมบูรณ์ของ NP สำหรับ เวอร์ชันที่ซับซ้อนยิ่งขึ้นซึ่งโดยสัญชาตญาณดูเหมือนยากขึ้นและอาจง่ายกว่าที่จะพิสูจน์ได้ยาก

Ilango ให้เครดิตความสนใจของเขาในความซับซ้อนของเมตาดาต้า เอริค อัลเลนเดอร์นักทฤษฎีความซับซ้อนที่มหาวิทยาลัย Rutgers และเป็นหนึ่งในนักวิจัยไม่กี่คนที่ยังคงทำงานเกี่ยวกับความซับซ้อนของเมตาดาต้าในช่วงทศวรรษปี 2000 และต้นปี 2010 “ความกระตือรือร้นของเขาแพร่เชื้อได้” Ilango กล่าว

นักวิจัยรุ่นเยาว์อีกคนที่ได้รับแรงบันดาลใจจากอัลเลนเดอร์ก็คือ ชูอิจิ ฮิราฮาระซึ่งปัจจุบันเป็นศาสตราจารย์ที่สถาบันสารสนเทศแห่งชาติในกรุงโตเกียว ในขณะที่ยังเป็นนักศึกษาระดับบัณฑิตศึกษาในปี 2018 Hirahara ได้เปิดเผยขอบเขตที่แท้จริงของความสัมพันธ์ระหว่างความซับซ้อนของเมตาดาต้าและความซับซ้อนของกรณีโดยเฉลี่ยที่ Carmosino และผู้เขียนร่วมของเขาได้ค้นพบ นักวิจัยทั้งสี่คนได้ค้นพบความเชื่อมโยงระหว่างความซับซ้อนของกรณีโดยเฉลี่ยของปัญหาหนึ่ง – MCSP – และความซับซ้อนกรณีที่เลวร้ายที่สุดของอีกปัญหาหนึ่ง – การเรียนรู้แบบบูลีน ฮิราฮาระได้พัฒนาเทคนิคของตนต่อไป ได้มา กรณีที่แย่ที่สุดถึงการลดกรณีที่เฉลี่ยสำหรับ MCSP ผลลัพธ์ของเขาบอกเป็นนัยว่าอัลกอริธึม MCSP กรณีโดยเฉลี่ยตามสมมุติฐานอย่างเช่นที่ Carmosino และเพื่อนร่วมงานของเขาเคยพิจารณาไว้จะมีพลังมากพอที่จะแก้ไข MCSP เวอร์ชันที่แตกต่างกันเล็กน้อยโดยไม่ทำผิดพลาดใดๆ

ผลลัพธ์ของ Hirahara นั้นน่าตื่นเต้นเพราะนักวิจัยหลายคนสงสัยว่า MCSP นั้นสมบูรณ์ ซึ่งแตกต่างจากปัญหาอื่นๆ ทั้งหมดที่ทราบการลดขนาดกรณีที่แย่ที่สุดถึงค่าเฉลี่ย หากพวกเขาสามารถขยายผลลัพธ์ของ Hirahara ให้ครอบคลุมอัลกอริธึมกรณีเฉลี่ยทั้งหมดแล้วพิสูจน์ว่า MCSP นั้นสมบูรณ์ NP นั่นก็จะพิสูจน์ได้ว่าเราไม่ได้อาศัยอยู่ใน Heuristica

“นั่นจะเป็นผลลัพธ์ที่น่าสะเทือนใจจริงๆ” สันทนามกล่าว

การพิสูจน์ว่า MCSP สมบูรณ์ NP อาจดูเหมือนเป็นคำสั่งที่สูง อย่างไรก็ตาม คำถามนี้เปิดมานานกว่า 50 ปีแล้ว แต่หลังจากก ความก้าวหน้า เมื่อปีที่แล้วโดย Hirahara นักวิจัยได้ใกล้ชิดกันมากกว่าที่ใครๆ จะคาดไว้เมื่อไม่กี่ปีก่อน

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

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

ผลลัพธ์นี้กระตุ้นให้นักวิจัยในเรื่องความซับซ้อนของเมตาดาต้ามากกว่างานก่อนหน้าของ Hirahara และนักวิจัยคนอื่น ๆ ก็สังเกตเห็นเช่นกัน - นักทฤษฎีความซับซ้อนและบล็อกเกอร์ Lance Fortnow ขนานนามมันว่า ผลลัพธ์ของปี. นั่นเป็นเพราะว่าการจัดการปัญหาการคำนวณเวอร์ชัน "ฟังก์ชันบางส่วน" ดังกล่าวเป็นขั้นตอนกลางที่สำคัญในการพิสูจน์ความสมบูรณ์ของ NP อื่นๆ

“มันเป็นงานที่น่าอัศจรรย์” วิลเลียมส์กล่าว “ทุกคนคิดว่าปัญหาบางส่วนเหล่านี้มีความยากพอๆ กันกับปัญหาทั้งหมด”

อุปสรรคยังคงพิสูจน์ความสมบูรณ์ของ NP สำหรับ MCSP เวอร์ชันเต็ม แต่ไม่มีอุปสรรคใดที่แนะนำว่าจำเป็นต้องมีชุดเครื่องมือใหม่ทั้งหมด อาจเป็นเพียงเรื่องของการค้นหาวิธีที่ถูกต้องในการรวมเทคนิคที่รู้จักเข้าด้วยกัน ในที่สุดการพิสูจน์ก็จะยุติสถานะของหนึ่งในไม่กี่ปัญหาที่ต่อต้านการจำแนกประเภทตราบใดที่ทฤษฎีความซับซ้อนยังคงอยู่ เลวินเขียนผ่านอีเมลว่า “มันคงจะทำให้ฉันถ่อมตัวโดยแสดงว่าฉันโง่ที่ไม่สามารถมองเห็นมันได้ :-)”

ชิ้นส่วนที่หายไป

MCSP ไม่ใช่ปัญหาเมตาที่ซับซ้อนเพียงปัญหาเดียวที่กระตุ้นให้เกิดความก้าวหน้าครั้งสำคัญ ในปี 2020 นักเข้ารหัสของ Cornell Tech ราฟาเอลพาส และนักศึกษาปริญญาโทของเขา หยานยี่ หลิว ค้นพบความเชื่อมโยง ระหว่างปัญหาเมตาที่ซับซ้อนที่แตกต่างกันและโปรโตคอลการเข้ารหัสพื้นฐานที่กำหนดขอบเขตระหว่าง Heuristica และ Pessiland ซึ่งเป็นโลกที่เลวร้ายที่สุดของ Impagliazzo (โดยที่ปัญหา NP ที่สมบูรณ์นั้นยากในกรณีทั่วไป แต่การเข้ารหัสยังคงเป็นไปไม่ได้) นั่นทำให้ปัญหาที่พวกเขาศึกษาคือผู้สมัครคนสำคัญในการโจมตีเพสซิแลนด์และพวกเขาด้วย งานล่าสุดเพิ่มเติม บ่งชี้ว่าสามารถต่อต้าน Heuristica ได้เช่นกัน

“ชิ้นส่วนต่างๆ ของปริศนาหายไป” พาสกล่าว “สำหรับฉันมันเป็นเรื่องมหัศจรรย์ที่สาขาเหล่านี้เชื่อมโยงกันอย่างใกล้ชิด”

ฮิราฮาระเตือนว่าความท้าทายยังคงรอนักวิจัยที่มีจุดประสงค์ในการคัดแยกโลกที่อิมพากลิอาซโซเสกเมื่อ 30 ปีที่แล้ว “ผมอยากจะบอกว่า ณ จุดหนึ่ง Heuristica และ Pessiland จะถูกตัดออก แต่ผมไม่แน่ใจว่าเราอยู่ใกล้แค่ไหน” เขากล่าว

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

“ผมพยายามที่จะไม่ปล่อยให้ตัวเองเป็นผู้ศรัทธามากเกินไป เพราะมีประวัติที่ค่อนข้างมั่นคงว่าไม่มีอะไรได้ผล” เขากล่าว “แต่เราเห็นการพัฒนาที่น่าตื่นเต้นมากมาย – วิธีเอาชนะสิ่งต่าง ๆ ที่ดูเหมือนเป็นอุปสรรค”

หากมีบทเรียนหนึ่งที่นักวิจัยได้เรียนรู้จากการต่อสู้ดิ้นรนเพื่อตอบคำถาม P กับ NP หรือแม้กระทั่งทำความเข้าใจ แสดงว่าทฤษฎีความซับซ้อนนั้นซับซ้อนในตัวมันเอง แต่ความท้าทายนั้นคือสิ่งที่ทำให้ภารกิจนี้คุ้มค่ามาก

“มันเป็นเรื่องที่ดีจริงๆ ว่ามันยากมาก” คาร์โมซิโนกล่าว “ฉันจะไม่เบื่อเลย”

หมายเหตุบรรณาธิการ: Scott Aaronson เป็นสมาชิกของ นิตยสาร Quanta's คณะกรรมการที่ปรึกษา.