ตรวจกับหา
คืนฝนตก ไรเดอร์ของฉันได้ออเดอร์ 15 ที่ในรอบเดียว ไรเดอร์อีกคนในกลุ่มแชตส่งลำดับมาให้ บอกว่าทางนี้วนครบทุกที่ได้ไม่เกิน 30 กิโลเมตร
ฉันตรวจได้ทันที บวกระยะทาง 15 ช่วง ได้ 28 กิโลเมตร จริงตามที่เขาว่า
ตรวจทางที่มีคนยื่นให้ ใช้แค่การบวกไม่กี่ครั้ง แต่ถ้าต้องหาเองว่ามีทางที่ไม่เกิน 25 กิโลเมตรไหม ยังไม่มีใครในโลกรู้วิธีที่เร็ว สำหรับโจทย์แบบนี้ทุกข้อ เมื่อจำนวนที่ส่งเพิ่มขึ้นเรื่อยๆ
15 ที่ที่ต้องวนกลับจุดเดิม มีลำดับให้เลือกกว่า 43,000 ล้านแบบ ข้อเหวี่ยงหมุนครบได้ ถ้ามีเวลาพอ นักคณิตศาสตร์มีวิธีที่ฉลาดกว่าการลองทุกลำดับมาตั้งแต่ทศวรรษ 1960 แต่ทุกวิธีที่รู้จักและได้คำตอบแน่นอนทุกครั้ง ยังโตเร็วจนตามไม่ทันเมื่อจำนวนที่ส่งเพิ่มขึ้น
๏
ช่องว่างระหว่างการตรวจกับการหา มีคนเห็นมันชัดๆ ครั้งแรกในจดหมายฉบับหนึ่ง
วันที่ 20 มีนาคม 1956 ที่พรินซ์ตัน เคิร์ท เกอเดล ชายที่เคยพูดสั้นๆ ในช่วงถามตอบที่เคอนิกส์แบร์กเมื่อ 26 ปีก่อน เขียนจดหมายถึงจอห์น ฟอน นอยมันน์ ซึ่งตอนนั้นป่วยหนักด้วยมะเร็ง
จดหมายเริ่มด้วยความเสียใจที่ได้ยินว่าเพื่อนป่วย แล้วจึงเข้าเรื่องคณิตศาสตร์
เกอเดลถามว่า ถ้ามีเครื่องที่รับข้อความทางคณิตศาสตร์ข้อหนึ่ง กับตัวเลข n แล้วตัดสินว่าข้อความนั้นมีบทพิสูจน์ยาวไม่เกิน n หรือไม่ เครื่องที่ดีที่สุดจะต้องใช้กี่ขั้น
ถ้าจำนวนขั้นโตแค่ประมาณ n หรือ n ยกกำลังสอง เขาเขียนว่าผลที่ตามมาจะสำคัญที่สุด งานทางปัญญาของนักคณิตศาสตร์กับคำถามแบบใช่หรือไม่ใช่ จะถูกแทนด้วยเครื่องได้ทั้งหมด ยกเว้นการตั้งสัจพจน์
๏
นั่นคือความหวังของฉันตั้งแต่คืนแรก เขียนโดยคนที่ไม่ได้หวัง แค่ถาม
เพราะเกอเดลกำหนดความยาวไว้ไม่เกิน n บทพิสูจน์ที่ต้องลองจึงมีจำนวนจำกัด เครื่องหาได้เสมอด้วยการลองทีละบท ถ้าไม่กำหนดความยาว คำถามจะกลับไปเป็นแบบที่ไม่มีขั้นตอนไหนตอบได้ทุกครั้ง แต่นั่นคือการเดินทุกทางในเมือง ไม่ใช่การเห็นทางลัด สิ่งที่เกอเดลถามคือ มีวิธีที่ไม่ต้องลองทุกทางไหม ถ้ามี การเห็นทางลัด ซึ่งเป็นงานที่ฉันเคยคิดว่าต้องมีคนทำทุกครั้ง ก็จะกลายเป็นการหมุนที่เร็วพอจะใช้ได้จริง
ไม่มีบันทึกว่าฟอน นอยมันน์ตอบ เขาตายในเดือนกุมภาพันธ์ปีถัดมา จดหมายฉบับนั้นเงียบอยู่หลายสิบปี จนมีคนเขียนถึงมันในปี 1989
๏
ระหว่างนั้น โลกถามคำถามเดียวกันใหม่ โดยไม่รู้ว่าเกอเดลถามไว้แล้ว
ปี 1971 สตีเฟน คุก นักวิทยาการคอมพิวเตอร์ ตั้งคำถามนี้ในรูปที่ใช้กันทุกวันนี้ เลโอนิด เลวิน ในสหภาพโซเวียต ไปถึงความคิดเดียวกันเอง และพิมพ์เป็นภาษารัสเซียในปี 1973 ปีถัดจากคุก ริชาร์ด คาร์ป แสดงว่าโจทย์ 21 ข้อที่ดูไม่เกี่ยวกัน รวมถึงการหาเส้นทางที่ผ่านทุกเมืองครั้งเดียว ยากเท่ากันหมด ถ้าใครหาวิธีเร็วสำหรับข้อหนึ่งเจอ ก็ได้วิธีเร็วของทุกข้อไปด้วย
ชื่อของคำถามนี้คือ P vs NP
ปี 2000 สถาบันคณิตศาสตร์เคลย์ตั้งรางวัลให้มัน ถ้าประกาศรางวัลนี้ติดบอร์ดหน้าห้าง มันจะหน้าตาแบบนี้
รับสมัครด่วน ค่าตอบแทน 1 ล้านดอลลาร์ งาน: เลือกนักศึกษา 100 คนจากผู้สมัคร 400 คนเข้าหอพัก ห้ามมีคู่ไหนในรายชื่อคู่ที่เข้ากันไม่ได้ที่คณบดีให้มา ตรวจคำตอบ: ง่าย ไล่ดูรายชื่อคู่ทีละคู่ หาคำตอบ: วิธีเลือก 100 จาก 400 มีมากกว่าจำนวนอะตอมในเอกภพที่รู้จัก คุณสมบัติ แสดงว่ามีวิธีหาที่เร็วสำหรับโจทย์แบบนี้ทุกข้อ หรือพิสูจน์ว่าไม่มี สถานะ ยังว่าง ตั้งแต่ปี 2000
ตัวอย่างหอพักเป็นตัวอย่างของเคลย์เอง หน้าเว็บของสถาบันอธิบายโจทย์นี้ว่า P คือสิ่งที่หาง่าย NP คือสิ่งที่ตรวจง่าย และถามว่าสองอย่างนี้เป็นอย่างเดียวกันหรือเปล่า
๏
ยังไม่มีใครรู้คำตอบ ที่มีคือการสำรวจความเห็น
นักวิทยาการคอมพิวเตอร์ชื่อวิลเลียม แกสาร์ช ถามนักทฤษฎีไปสามรอบ ในรอบปี 2002 จาก 100 คนที่ตอบ 61 คนเชื่อว่าการหายากกว่าการตรวจจริง และอีก 22 คนตอบว่าไม่รู้ ในรอบปี 2019 จาก 124 คน 109 คนเชื่อแบบนั้น รอบนั้นไม่มีใครตอบว่าไม่รู้ แต่แกสาร์ชเขียนเองว่าอาจเป็นเพราะแบบสอบถามออนไลน์ที่เขาใช้ไม่ค่อยเปิดช่องให้ตอบอย่างอื่น
ความเชื่อไม่ใช่บทพิสูจน์ มันเป็นแค่สิ่งที่คนที่ใกล้ปัญหาที่สุดเดิมพันไว้
และถ้าวันหนึ่งพิสูจน์ได้ว่าการหายากกว่าการตรวจจริง ก็ไม่ได้แปลว่าออเดอร์ 15 ที่ของไรเดอร์ของฉันหมดหวัง โจทย์เล็กยังหาได้ คำตอบที่ดีพอยังหาได้ สิ่งที่ไม่มีคือวิธีเดียวที่หาคำตอบดีที่สุดได้เร็วทุกครั้ง ไม่ว่าโจทย์จะใหญ่แค่ไหน
เมื่อตัวเลือกมีจำนวนจำกัดและตรวจได้ ข้อเหวี่ยงหาคำตอบได้เสมอถ้าลองทุกตัว คำถามคือมันหาได้เร็วเท่าที่ตรวจได้ไหม และยังไม่มีใครรู้
๏
ฉันบอกไรเดอร์ของฉันว่า ฉันลองมาสามวินาที เจอทางราว 26 กิโลเมตร สั้นกว่าทางในแชตราว 2 กิโลเมตร มันดีพอ แต่ฉันไม่รู้ว่ามีทางที่ไม่เกิน 25 กิโลเมตรไหม
เขาเลือกทางของฉันไปแปดที่ แล้วเลี้ยวเข้าซอยที่ฉันไม่รู้จักสำหรับอีกเจ็ดที่
คำถามของฉันตั้งแต่คืนแรกคือ การเห็นเขียนเป็นขั้นตอนได้ไหม ตอนนี้ฉันรู้ว่าคำถามนั้นมีญาติที่คมกว่า ไม่ใช่ว่าเครื่องหาได้ไหม แต่หาได้โดยไม่ต้องลองทุกทางไหม และญาติตัวนั้นมีชื่อ มีเงินรางวัล และมีนักคณิตศาสตร์หลายรุ่นนั่งอยู่หน้ามันมาเกิน 50 ปีโดยยังไม่ได้คำตอบ
ฉันอยากเล่าเรื่องนี้ให้เจ๊เพ็ญฟัง แต่ร้านใกล้ปิดแล้ว และเธอกำลังนับเงินทั้งวันด้วยลูกคิด
บทถัดไป · 9 / 10นับปิดร้าน