หน้าแรก › คณิตศาสตร์ › P กับ NP: ตรวจง่าย แต่หายาก
คณิตศาสตร์ · เทคโนโลยี
P กับ NP: ตรวจง่าย แต่หายาก
คำถามล้านดอลลาร์เรื่องโจทย์ยาก
การตรวจซูโดกุที่เติมเสร็จแล้วใช้เวลาแค่นาทีเดียว แต่การหาคำตอบอาจนานกว่านั้นมาก ช่องว่างนี้มีอยู่จริง หรือเราแค่ยังหาเคล็ดลับไม่เจอ นี่คือหนึ่งในคำถามใหญ่ที่ยังไม่มีคำตอบของคณิตศาสตร์ มีรางวัลหนึ่งล้านดอลลาร์ และสัปดาห์นี้แล็บ AI อ้างว่าล้มข้อสันนิษฐานหนึ่งที่สร้างขึ้นรอบคำถามนี้ได้
หนังสามมิติโต้ตอบได้ 10 นาที 1956 ถึง ปัจจุบัน เผยแพร่ 28 ตุลาคม 2569
อ่านฉบับ English
สารบัญ บทนำ บทที่ I · ตรวจกับหา บทที่ II · เร็วกับช้า บทที่ III · คำถาม บทที่ IV · ได้หมดหรือไม่ได้เลย บทที่ V · ทำไมจึงสำคัญ บทที่ VI · ข้ออ้างใหม่ บทส่งท้าย บทนำ คณิตศาสตร์ · เทคโนโลยี
ตรวจง่าย แต่หายาก หรือไม่ใช่? คำถามล้านดอลลาร์
วันที่ 26 ตุลาคม 2026 OpenAI ประกาศว่าโมเดล AI ของตนล้มข้อสันนิษฐานที่คนเชื่อกันกว้างขวาง ว่าปริศนาตรรกะบางแบบยากแค่ไหน ไม่กี่ชั่วโมงต่อมา Anthropic ก็บอกว่าโมเดลของตนทำได้เหมือนกัน
งานวิจัยหลายร้อยชิ้นตั้งอยู่บนข้อสันนิษฐานนั้น นักวิทยาการคอมพิวเตอร์ชั้นนำจึงกำลังตรวจสอบทั้งสองข้ออ้างอย่างเปิดเผย และยังไม่มีใครยืนยัน
จะเข้าใจว่าทำไมเรื่องนี้สำคัญ ต้องเริ่มจากปริศนาง่าย ๆ และคำถามที่มีค่าหนึ่งล้านดอลลาร์
ETH สมมติฐานเวลาเลขชี้กำลัง เสนอในปี 1999
หลายร้อย งานวิจัยวิทยาการคอมพิวเตอร์ที่อาศัยมัน (TNW) ข้อสันนิษฐานที่ถูกท้าทาย “การเข้าร่วมของเราไม่ควรถูกตีความว่าเป็นการรับรองข้ออ้างนี้”จดหมายเปิดผนึกของนักวิทยาการคอมพิวเตอร์ผู้ตรวจสอบ ผ่าน The Next Web ทำไมการตรวจจึงง่ายกว่าการหา อัลกอริทึมเร็วและช้า P, NP และ NP-complete ข้ออ้างใหม่จะเปลี่ยนอะไร ในภาพยนตร์นี้ บทที่ I · ตรวจกับหา บทที่ I
ตรวจกับหา อย่างหนึ่งเร็ว อีกอย่างอาจไม่เร็ว
นี่คือซูโดกุที่เติมเสร็จแล้ว การตรวจทำได้แค่ไล่ดูแต่ละแถว แต่ละคอลัมน์ และแต่ละช่องใหญ่ว่ามีเลขซ้ำไหม ใช้เวลาแค่นาทีเดียว
แต่การหาคำตอบจากตารางที่เกือบว่างเป็นอีกเรื่องหนึ่ง เราลองใส่เลข ถอยกลับ แล้วลองใหม่ และยิ่งตารางใหญ่ขึ้น ความเป็นไปได้ก็ยิ่งเพิ่มขึ้นแบบก้าวกระโดด
การตรวจนั้นง่าย การหาดูเหมือนจะยาก ภาพยนตร์ทั้งเรื่องนี้คือคำถามว่าความต่างนั้นมีอยู่จริงหรือไม่
9 แถว: ไม่มีเลขซ้ำ 9 คอลัมน์: ไม่มีเลขซ้ำ 9 ช่องใหญ่: ไม่มีเลขซ้ำ กดปุ่ม “ตรวจ” ในฉาก การตรวจซูโดกุ แก้ด้วยมือ ดินสอเหนือตารางปริศนา สำหรับซูโดกุทั่วไปขนาด n² × n² การหาคำตอบเป็นปัญหา NP-complete (Fortnow, 2009) ภาพประกอบสร้างด้วย AI
ตรวจ ไล่ตารางรอบเดียว
หา อาจต้องค้นตัวเลือกนับไม่ถ้วน ความต่าง สถาบันคณิตศาสตร์เคลย์ยกอีกตัวอย่างหนึ่ง 13,717,421 เป็นผลคูณของจำนวนที่เล็กกว่าสองจำนวนหรือไม่ การหาด้วยมืออาจใช้เวลานานมาก
แต่ถ้ามีคนบอกคำตอบว่า 3,607 คูณ 3,803 เราจะตรวจได้ด้วยเครื่องคิดเลขในไม่กี่วินาที
ปัญหาในชีวิตจริงหลายอย่างมีรูปแบบนี้ คำตอบที่ดีอาจหายาก แต่พอเห็นแล้วก็รู้ได้ทันที
ด้วยมือ หรือด้วยเครื่อง เครื่องคิดเลขกลไกรุ่นเก่า ถ้าลองหารทีละตัว จะไปถึง 3,607 ได้หลังลองจำนวนเฉพาะไปแล้วหลายร้อยตัว ภาพประกอบสร้างด้วย AI3607 × 3803 = 13 717 421 3607 \times 3803 = 13\,717\,421 3607 × 3803 = 13 717 421 3607 , 3803 3607,\ 3803 3607 , 3803 ตัวประกอบสองตัว: หายาก แต่ตรวจง่าย เส้นทางส่งของที่ไม่เกินระยะทางที่กำหนด ตารางเวลาที่ไม่ชนกัน การจัดของให้ไม่เกินน้ำหนักที่กำหนด หายาก แต่ตรวจง่าย บทที่ II · เร็วกับช้า บทที่ II
เร็วกับช้า งานเพิ่มขึ้นอย่างไร คือตัวตัดสินทุกอย่าง
นักวิทยาการคอมพิวเตอร์ตัดสินอัลกอริทึมจากว่าเวลาทำงานเพิ่มขึ้นอย่างไรเมื่อโจทย์ใหญ่ขึ้น ถ้าข้อมูลมี n ส่วน วิธีที่เร็วอาจใช้ราว n กำลังสองขั้น
ปี 1965 แจ็ก เอ็ดมอนด์ส เสนอว่าอัลกอริทึมที่ดีคืออัลกอริทึมที่จำนวนขั้นไม่เกินพหุนามที่ตายตัวของขนาดข้อมูล เช่น n กำลังสอง หรือ n กำลังสาม
วิธีแบบเลขชี้กำลังต่างออกไป จำนวนขั้นเพิ่มแบบสองยกกำลัง n คือทุกส่วนที่เพิ่มขึ้นหนึ่งส่วน งานจะเพิ่มเป็นสองเท่า
เมื่อ n เท่ากับสิบ n กำลังสองคือหนึ่งร้อย และสองยกกำลัง n ราวหนึ่งพัน แต่เมื่อ n เท่ากับหนึ่งร้อย n กำลังสองคือหนึ่งหมื่น ขณะที่สองยกกำลัง n เป็นจำนวนที่มีสามสิบเอ็ดหลัก
n 2 (polynomial) n^2 \quad \text{(polynomial)} n 2 (polynomial) 2 n (exponential) 2^n \quad \text{(exponential)} 2 n (exponential) n n n ขนาดของข้อมูล
“Paths, trees, and flowers” บทความที่มีอัลกอริทึมเร็วสำหรับการจับคู่ แจ็ก เอ็ดมอนด์ส ปี 1965
2¹⁰ = 1,024 n = 10
2¹¹ = 2,048 n = 11
2¹² = 4,096 n = 12 เพิ่มเป็นสองเท่าทุกขั้น n² 10,000 n³ 1,000,000 2ⁿ ≈ 1.27 × 10³⁰
จำนวนขั้นเมื่อ n = 100 (แสดงจำนวนหลัก) นี่คือปริศนาแบบที่อยู่ใจกลางข่าว สูตรตรรกะมีสวิตช์ n ตัว แต่ละตัวเป็นจริงหรือเท็จ พร้อมรายการกฎเกี่ยวกับมัน มีวิธีตั้งสวิตช์ที่ทำตามกฎได้ทุกข้อหรือไม่
นี่เรียกว่าปัญหาการทำให้สูตรเป็นจริงได้ (satisfiability) หรือ SAT การตรวจวิธีตั้งที่เสนอมาทำได้เร็ว แค่ไล่ดูกฎทีละข้อ
แต่วิธีหาที่ตรงไปตรงมาที่สุดคือลองทุกแบบ และสวิตช์ n ตัวมีวิธีตั้งสองยกกำลัง n แบบ เพิ่มสวิตช์สิบตัว ก็ต้องลองมากขึ้นราวหนึ่งพันเท่า
สวิตช์ n ตัว: จริงหรือเท็จ กฎเช่น “A หรือ ไม่ใช่ B หรือ C” เป้าหมาย: ทำตามกฎทุกข้อพร้อมกัน ปริศนา SAT ทุกการผสม แผงสวิตช์โยกรุ่นเก่า ถ้ามี 30 สวิตช์ ก็มีวิธีตั้งราว 1.07 พันล้านแบบแล้ว ภาพประกอบสร้างด้วย AI
1,024 n = 10
≈ 1.07 พันล้าน n = 30
≈ 1.27 × 10³⁰ n = 100 วิธีตั้งสวิตช์ n ตัว 2 n + 10 = 1024 × 2 n 2^{n+10} = 1024 \times 2^{n} 2 n + 10 = 1024 × 2 n + 10 +10 + 10 สวิตช์เพิ่มสิบตัว บทที่ III · คำถาม บทที่ III
คำถาม ทุกอย่างที่ตรวจได้เร็ว หาได้เร็วด้วยไหม
ทีนี้มาดูสองตระกูล P คือกลุ่มปัญหาที่แก้ได้ในเวลาพหุนาม หรือปัญหาที่เรานับว่าจัดการได้
NP คือกลุ่มปัญหาที่คำตอบที่เสนอมาตรวจสอบได้ในเวลาพหุนาม ซูโดกุ SAT และปริศนาการแยกตัวประกอบล้วนอยู่ใน NP
ทุกปัญหาใน P อยู่ใน NP ด้วย ถ้าหาคำตอบได้เร็ว ก็ย่อมตรวจได้เร็วแน่นอน คำถามที่ยังเปิดอยู่คือทิศทางกลับกัน
ถ้าทุกปัญหาที่ตรวจได้เร็วแก้ได้เร็วด้วย ก็แปลว่า P เท่ากับ NP นักวิจัยส่วนใหญ่คิดว่าไม่ใช่ แต่ยังไม่มีใครพิสูจน์ได้ทั้งสองทาง
แก้ได้ในเวลาพหุนาม ตัวอย่าง: เรียงลำดับรายการ ตัวอย่าง: หาเส้นทางที่สั้นที่สุด P ตรวจคำตอบได้ในเวลาพหุนาม รวม P ทั้งหมดไว้ รวม SAT ซูโดกุ และการแยกตัวประกอบ NP ย่อมาจาก “nondeterministic polynomial time” ไม่ได้แปลว่า “ไม่ใช่พหุนาม” NP P ⊆ N P \mathrm{P} \subseteq \mathrm{NP} P ⊆ NP P = ? N P \mathrm{P} \overset{?}{=} \mathrm{NP} P = ? NP ⊆ \subseteq ⊆ “อยู่ภายใน”
ยังเปิดอยู่ ยังไม่มีบทพิสูจน์ทั้งสองทาง
1 ล้านดอลลาร์ รางวัลของเคลย์สำหรับบทพิสูจน์ที่ถูกต้อง สถานะวันนี้ คำถามนี้เก่ากว่าคอมพิวเตอร์ส่วนใหญ่ ปี 1956 นักตรรกศาสตร์ เคิร์ท เกอเดิล เขียนจดหมายถึงจอห์น ฟอน นอยมันน์ ซึ่งกำลังป่วยหนักใกล้เสียชีวิต
เขาถามว่างานของเครื่องจักรจะเพิ่มเร็วแค่ไหน ถ้าต้องตัดสินว่าข้อความหนึ่งมีบทพิสูจน์ที่ยาวตามที่กำหนดหรือไม่ ถ้างานเพิ่มช้า เขาเขียนว่า ความพยายามทางความคิดของนักคณิตศาสตร์กับคำถามแบบใช่หรือไม่ใช่จะถูกแทนด้วยเครื่องจักรได้ และจะมีผลตามมามหาศาลที่สุด
จดหมายระหว่างสองอัจฉริยะ จดหมายและปากกาหมึกซึมยุค 1950 ต้นฉบับจดหมายของเกอเดิลเก็บไว้ที่หอสมุดรัฐสภาสหรัฐฯ (Sipser) ภาพประกอบสร้างด้วย AI“…ผลตามมาที่มหาศาลที่สุด”เคิร์ท เกอเดิล ถึงจอห์น ฟอน นอยมันน์ ปี 1956 (คำแปลใน Sipser, 1992) 1955 จอห์น แนช คาดว่าเวลาถอดรหัสโตแบบเลขชี้กำลังตามความยาวกุญแจ1956 จดหมายของเกอเดิล1965 เอ็ดมอนด์ส: มีประสิทธิภาพ = พหุนามก่อนคำถามจะมีชื่อ บทที่ III · คำถาม
จดหมายที่ถูกลืมของเกอเดิล
Sipser (1992): ปี 1956 เกอเดิลเขียนถึงฟอน นอยมันน์ ซึ่งป่วยหนักใกล้เสียชีวิต ถามว่าจำนวนขั้นของเครื่องจักรที่ตัดสินว่าสูตรหนึ่งมีบทพิสูจน์ยาว n หรือไม่ จะเพิ่มเร็วแค่ไหน เพิ่มแบบ Kn หรือ Kn² หรือเปล่า ถ้าเป็นเช่นนั้น เขาเขียนว่า ความพยายามทางความคิดของนักคณิตศาสตร์กับคำถามแบบใช่หรือไม่ใช่จะถูกแทนที่ด้วยเครื่องจักรได้ทั้งหมด และจะมี “ผลตามมาที่มหาศาลที่สุด” ต้นฉบับจดหมายอยู่ที่หอสมุดรัฐสภาสหรัฐฯ Wikipedia: ปี 1955 จอห์น แนช เขียนถึงสำนักงานความมั่นคงแห่งชาติสหรัฐฯ คาดว่าเวลาที่ใช้ถอดรหัสจะเพิ่มแบบเลขชี้กำลังตามความยาวกุญแจ แม้เขาเองสงสัยว่าจะพิสูจน์ได้
สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง
แหล่งข้อมูล:
Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds) ;
Wikipedia: P versus NP problem (consequences) บทที่ IV · ได้หมดหรือไม่ได้เลย บทที่ IV
ได้หมดหรือไม่ได้เลย ปัญหามากมาย ชะตาเดียวกัน
ปี 1971 สตีเฟน คุก พิสูจน์สิ่งที่น่าทึ่ง ทุกปัญหาใน NP แปลงเป็น SAT หรือปริศนาสวิตช์ได้อย่างรวดเร็ว ดังนั้นถ้ามีวิธีแก้ SAT ได้เร็ว ก็จะมีวิธีแก้ทุกปัญหาใน NP ได้เร็วด้วย
ปัญหาที่มีคุณสมบัตินี้เรียกว่า NP-complete และ SAT คือปัญหาแรก ลีโอนิด เลวิน ค้นพบแนวคิดเดียวกันอย่างอิสระและตีพิมพ์ในปี 1973
ต่อมาคุกได้รับรางวัลทัวริงจากงานนี้ ซึ่งมักถูกเรียกว่ารางวัลโนเบลของวงการคอมพิวเตอร์
1971 คุก ในการประชุม ACM STOC
1973 เลวิน อย่างอิสระ ทฤษฎีบทคุก–เลวิน อยู่ใน NP ทุกปัญหา NP แปลงมาเป็นมันได้เร็ว แก้มันได้เร็ว ก็แก้ NP ทั้งหมดได้เร็ว NP-complete หมายถึง การยอมรับ ถ้วยรางวัลเรียบ ๆ บนโต๊ะที่มีกองกระดาษ คุกได้รับรางวัลทัวริงในปี 1982 ภาพประกอบสร้างด้วย AIบทที่ IV · ได้หมดหรือไม่ได้เลย
ปัญหา NP-complete ปัญหาแรก
ACM: บทความ “The complexity of theorem-proving procedures” ของสตีเฟน คุก ซึ่งนำเสนอในการประชุม ACM Symposium on Theory of Computing (STOC) ครั้งที่ 3 ปี 1971 แสดงว่า SAT เป็น NP-complete และเป็นปัญหาแรกของกลุ่มนี้ ลีโอนิด เลวิน ค้นพบแนวคิดเดียวกันอย่างอิสระ (ตีพิมพ์ปี 1973) คุกได้รับรางวัลทัวริงในปี 1982 Britannica: ปัญหา NP-complete อยู่ใน NP และยากอย่างน้อยเท่ากับทุกปัญหาอื่นใน NP อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหาใดปัญหาหนึ่งจึงให้อัลกอริทึมที่มีประสิทธิภาพสำหรับทุกปัญหาใน NP
ลองดู: กด “แก้ SAT ได้เร็ว” แล้วดูคำตอบไหลไปตามการแปลงสู่ทุกปัญหาที่เชื่อมอยู่ เครือข่ายเป็นแผนภาพ ไม่ใช่แผนที่ครบถ้วนของการแปลงที่รู้จัก
สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง
แหล่งข้อมูล:
ACM A.M. Turing Award: Stephen A. Cook (1982) ;
Encyclopaedia Britannica: NP-complete problem ;
Encyclopaedia Britannica: P versus NP problem ปีต่อมา ริชาร์ด คาร์ป แสดงว่าปัญหาที่รู้จักกันดียี่สิบเอ็ดปัญหาเป็น NP-complete ด้วย รวมถึงการระบายสีเครือข่าย การหาเส้นทางวนที่ผ่านทุกจุดเพียงครั้งเดียว และการจัดของใส่เป้
หลังจากนั้นมีปัญหาอีกมากเข้ามาร่วมรายการ ทั้งปัญหาพนักงานขายเดินทางและซูโดกุตารางใหญ่ พวกมันจะง่ายหรือยากไปพร้อมกัน
ถ้าหาวิธีที่เร็วสำหรับปัญหาใดปัญหาหนึ่งได้ ก็จะมีวิธีสำหรับทุกปัญหา และ P เท่ากับ NP ถ้าพิสูจน์ได้ว่าปัญหาใดปัญหาหนึ่งไม่มีวิธีที่เร็ว P ก็ไม่เท่ากับ NP
ลองระบายสีเครือข่ายนี้ด้วยสามสี โดยจุดที่เชื่อมกันต้องไม่เป็นสีเดียวกัน การตรวจทำได้ทันที แต่การหาอาจต้องใช้เวลา
จำนวนสีน้อยที่สุด (chromatic number) วงจรแฮมิลตัน ปัญหาเป้ (knapsack) คลิก (clique) 3-SAT และอื่น ๆ จาก 21 ปัญหาของคาร์ป (1972) พนักงานขายเดินทาง หมุดและด้ายบนแผนที่เก่าที่ลากเป็นเส้นทาง การตรวจว่าเส้นทางที่ให้มาไม่เกินระยะทางที่กำหนดทำได้เร็ว ภาพประกอบสร้างด้วย AI
ข้อใดข้อหนึ่งเร็ว → เร็วทั้งหมด: P = NP
พิสูจน์ได้ว่าข้อหนึ่งช้า → P ≠ NP ได้หมดหรือไม่ได้เลย
19 จุด
3 สีที่ใช้ได้
3¹⁹ วิธีระบายที่เป็นไปได้: ราว 1.16 พันล้าน เครือข่ายในฉาก บทที่ V · ทำไมจึงสำคัญ บทที่ V
ทำไมจึงสำคัญ รางวัล และแม่กุญแจของอินเทอร์เน็ต
ปี 2000 สถาบันคณิตศาสตร์เคลย์จัดให้ปัญหา P กับ NP เป็นหนึ่งในเจ็ดปัญหารางวัลมิลเลนเนียม มีรางวัลหนึ่งล้านดอลลาร์สำหรับผู้ไขได้ ในเจ็ดปัญหานั้น มีเพียงข้อความคาดการณ์ของปวงกาเรข้อเดียวที่ถูกไขแล้ว
เดิมพันนี้ยังเป็นเรื่องในชีวิตจริงด้วย การเข้ารหัสยุคใหม่จำนวนมากตั้งอยู่บนความเชื่อว่าปัญหาบางอย่าง เช่น การแยกตัวประกอบผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัว แก้ได้เร็วไม่ได้
การแยกตัวประกอบอยู่ใน NP แต่ไม่เชื่อกันว่าเป็น NP-complete ดังนั้นแม้จะพิสูจน์ได้ว่า P ไม่เท่ากับ NP ก็ยังไม่ได้พิสูจน์ว่าการแยกตัวประกอบยาก
ทิศทางกลับกันชัดเจนกว่า อย่างที่นักวิทยาการคอมพิวเตอร์ แลนซ์ ฟอร์ตนาว กล่าวไว้ ถ้า P เท่ากับ NP การเข้ารหัสแบบกุญแจสาธารณะจะเป็นไปไม่ได้
7 ปัญหา ประกาศ 24 พฤษภาคม 2000 ที่ปารีส
1 ล้านดอลลาร์ ต่อปัญหา
1 ที่ไขได้แล้ว: ปวงกาเร ปัญหารางวัลมิลเลนเนียม (เคลย์) แม่กุญแจที่ทำจากตัวเลข แม่กุญแจบนตู้เซิร์ฟเวอร์ Britannica: การเข้ารหัสยุคใหม่อาศัยข้อสันนิษฐานว่าการแยกตัวประกอบไม่อยู่ใน P ภาพประกอบสร้างด้วย AIอยู่ใน NP: ตรวจคำตอบได้ง่าย ไม่เชื่อกันว่าเป็น NP-complete ความยากของมันเป็นข้อสันนิษฐาน ยังไม่ได้พิสูจน์ การแยกตัวประกอบ “ถ้า P = NP การเข้ารหัสแบบกุญแจสาธารณะจะเป็นไปไม่ได้”แลนซ์ ฟอร์ตนาว, Communications of the ACM, 2009 บทที่ V · ทำไมจึงสำคัญ
รางวัลและแม่กุญแจ
สถาบันคณิตศาสตร์เคลย์: ประกาศปัญหารางวัลมิลเลนเนียมวันที่ 24 พฤษภาคม 2000 ที่ Collège de France กรุงปารีส มีรางวัล 1 ล้านดอลลาร์ต่อปัญหา รวมเจ็ดปัญหา ข้อความคาดการณ์ของปวงกาเรเป็นข้อเดียวที่ไขได้แล้ว Britannica: การเข้ารหัสยุคใหม่สันนิษฐานว่าการแยกตัวประกอบผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัวไม่อยู่ใน P และวิธีแยกตัวประกอบที่มีประสิทธิภาพจะทำลายการเข้ารหัสยุคใหม่ส่วนใหญ่ Fortnow (2009): “ถ้า P = NP การเข้ารหัสแบบกุญแจสาธารณะจะเป็นไปไม่ได้” และไม่คาดว่าการแยกตัวประกอบกับลอการิทึมไม่ต่อเนื่องจะเป็น NP-complete
แม่กุญแจสามมิติเป็นอุปมา จำนวนเฉพาะสองตัวคูณกันเป็นจำนวนเดียวได้ง่าย แต่แยกกลับยาก
สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง
แหล่งข้อมูล:
Clay Mathematics Institute: The Millennium Prize Problems ;
Encyclopaedia Britannica: P versus NP problem ;
Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem ถ้า P เท่ากับ NP จริง และวิธีนั้นใช้ได้จริงในทางปฏิบัติ ปัญหาการวางแผนยาก ๆ จำนวนมากจะกลายเป็นเรื่องง่าย และคอมพิวเตอร์จะค้นหาบทพิสูจน์ของทฤษฎีบทได้ อย่างที่คุกเองเคยชี้ไว้
ผู้เชี่ยวชาญส่วนใหญ่ไม่เชื่อ ในการสำรวจนักวิจัย 124 คนของวิลเลียม แกสาร์ช ปี 2019 แปดสิบแปดเปอร์เซ็นต์เชื่อว่า P ไม่เท่ากับ NP และสิบสองเปอร์เซ็นต์เชื่อว่าเท่ากัน
แต่การสำรวจความเห็นไม่ใช่บทพิสูจน์ และข้ออ้างเดือนนี้ก็แสดงว่าแม้ความเชื่อที่คนส่วนใหญ่ยึดถือก็ถูกทดสอบได้ ลองดูทั้งสองโลก
ปัญหาเส้นทางและโลจิสติกส์แก้ได้อย่างมีประสิทธิภาพ คอมพิวเตอร์หาบทพิสูจน์ที่ยาวพอสมควรได้ การค้นหาในงานออกแบบและจัดตารางจำนวนมากจะเร็วขึ้น ถ้า P = NP (Wikipedia, Fortnow) นักวิจัยที่เชื่อว่า P ≠ NP (การสำรวจของแกสาร์ช) P ≠ NP: วงในยังเล็กอยู่ P = NP: วงในขยายเต็ม NP ยังไม่มีใครรู้ว่าเราอยู่ในโลกไหน ลองสองโลก บทที่ V · ทำไมจึงสำคัญ
ถ้าหาก?
Wikipedia สรุปจากงานวิชาการ: ถ้า P = NP ปัญหาโลจิสติกส์จำนวนมากเช่นพนักงานขายเดินทางจะแก้ได้อย่างมีประสิทธิภาพ และคอมพิวเตอร์จะหาบทพิสูจน์แบบรูปนัยของทฤษฎีบทที่มีบทพิสูจน์ยาวพอสมควรได้ ซึ่งคุกเคยอธิบายความเป็นไปได้นี้ไว้ การเข้ารหัสแบบกุญแจสาธารณะจะตกอยู่ในความเสี่ยง การสำรวจนักวิจัยของแกสาร์ช: 61% เชื่อว่า P ≠ NP ในปี 2002 (ผู้ตอบ 100 คน) 83% ในปี 2012 (152 คน) และ 88% ในปี 2019 (124 คน สำรวจปี 2018) ส่วนผู้ที่เชื่อว่า P = NP มี 9%, 9% และ 12%
บทพิสูจน์ว่า P = NP อาจให้อัลกอริทึมที่เป็นพหุนามแต่ช้าเกินจะใช้งาน ผลตามมาข้างต้นสมมติว่าวิธีนั้นใช้งานได้จริง ลองดู: สลับระหว่างสองโลก
สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง
แหล่งข้อมูล:
Wikipedia: P versus NP problem (consequences) ;
William Gasarch (2019): The third P =? NP poll ;
Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem บทที่ VI · ข้ออ้างใหม่ บทที่ VI
ข้ออ้างใหม่ เดิมพันที่หนักกว่า และเครื่องจักรที่ท้าทายมัน
สมมติฐานเวลาเลขชี้กำลังไปไกลกว่าคำถาม P กับ NP รัสเซลล์ อิมพากลิอัซโซ และรามาโมฮัน ปาตูรี วางมันไว้ในปี 1999 ว่า 3-SAT ซึ่งคือปริศนาสวิตช์ที่แต่ละกฎมีสวิตช์สามตัว แก้ในเวลาต่ำกว่าเลขชี้กำลังไม่ได้
พูดอีกอย่างคือ ทุกวิธีต้องใช้เวลาที่เพิ่มอย่างน้อยแบบสองยกกำลังเศษส่วนคงที่ของ n ซึ่งยังคงเพิ่มเป็นเท่าตัวในอัตราคงที่ วิธีที่ต่ำกว่าเลขชี้กำลังจะเพิ่มช้ากว่าทุกเส้นเหล่านั้น แต่ไม่จำเป็นต้องช้าเท่าพหุนาม
มันเป็นเดิมพันที่หนักกว่า P ไม่เท่ากับ NP เพราะถ้ามันจริง P ก็ไม่เท่ากับ NP ลองกดปุ่มเทียบเส้นโค้ง
งานวิจัยวิทยาการคอมพิวเตอร์หลายร้อยชิ้นตั้งอยู่บนสมมติฐานนี้ โดยใช้มันแสดงว่าปัญหาอื่นแก้ได้เร็วแค่ไหน และเร็วกว่านั้นไม่ได้
∃ δ > 0 : 3-SAT needs 2 δ n time \exists\, \delta > 0:\ \text{3-SAT needs } 2^{\delta n} \text{ time} ∃ δ > 0 : 3-SAT needs 2 δ n time δ \delta δ เศษส่วนบวกคงที่ค่าหนึ่ง n n n จำนวนสวิตช์ (ตัวแปร) 2 n , 2 n / 10 exponential 2^{n},\ 2^{n/10} \quad \text{exponential} 2 n , 2 n /10 exponential 2 n sub-exponential 2^{\sqrt{n}} \quad \text{sub-exponential} 2 n sub-exponential n 3 polynomial n^{3} \quad \text{polynomial} n 3 polynomial 2 n 2^{\sqrt{n}} 2 n ตัวอย่างในตำรา ไม่ใช่อัลกอริทึมที่ถูกอ้าง ETH จริง → P ≠ NP จริง ETH เท็จ → P กับ NP ยังเปิดอยู่ ETH เป็นข้อความที่เข้มกว่า P ≠ NP (MIT) เดิมพันซ้อนกันอย่างไร
หลายร้อย งานวิจัยวิทยาการคอมพิวเตอร์
1999 อิมพากลิอัซโซและปาตูรีเผยแพร่ครั้งแรก ตั้งอยู่บน ETH (TNW) OpenAI ระบุว่าโมเดลพบการหักล้างนี้วันที่ 16 ตุลาคม และวันถัดมาได้ตรวจด้วย Lean ซึ่งเป็นโปรแกรมตรวจบทพิสูจน์ทีละบรรทัด แล็บเหล่านี้อ้างว่ามีอัลกอริทึมที่แก้ปริศนาเหล่านี้ได้ในเวลาต่ำกว่าเลขชี้กำลัง
อิมพากลิอัซโซ ปาตูรี และไรอัน วิลเลียมส์ แห่ง MIT นำการตรวจสอบแบบเปิด วิลเลียมส์บอกว่าบางส่วนของบทพิสูจน์ดูเป็นเรื่องปกติ แต่มีบางส่วนแปลกพอที่ต้องอาศัยแรงของทั้งวงการ
OpenAI บอกว่าค่อนข้างมั่นใจว่าผลนี้ไม่ทำลายการเข้ารหัส และแม้มันจะถูกต้อง วิธีที่ต่ำกว่าเลขชี้กำลังก็ไม่ใช่วิธีแบบพหุนาม จึงยังไม่ได้แสดงว่า P เท่ากับ NP
วิลเลียมส์บอกว่ามันควรทำให้ความเป็นไปได้นั้นมีน้ำหนักขึ้นเล็กน้อย แต่เขาสงสัยว่าอัลกอริทึมนี้ยังไม่ใช่วิธีที่ดีที่สุด
อัลกอริทึมเวลาต่ำกว่าเลขชี้กำลังสำหรับปริศนา SAT เหล่านี้ บทพิสูจน์ตรวจด้วย Lean และเผยแพร่บน GitHub ยังไม่ได้รับการยืนยันโดยอิสระ สิ่งที่อ้าง การตรวจบทพิสูจน์ หน้ากระดาษพิมพ์และบันทึกบนโต๊ะสัมมนา ผู้ตรวจสอบขอให้ OpenAI เปิดเผยข้อมูลดิบทั้งหมดและสนับสนุนการประชุม ซึ่ง OpenAI ตกลง (TNW) ภาพประกอบสร้างด้วย AIETH เป็นเท็จ งานวิจัยที่สันนิษฐาน ETH ต้องทบทวนใหม่ P กับ NP ยังเปิดอยู่ ถ้าข้ออ้างถูกต้อง
OpenAI ประกาศ 26 ต.ค. บทพิสูจน์อยู่บน GitHub
Anthropic การหักล้างของตนบน GitHub ตามรายงาน TechCrunch สองข้ออ้าง การตรวจหนึ่งเดียว บทที่ VI · ข้ออ้างใหม่
อยู่ระหว่างการตรวจสอบ
The Next Web: OpenAI ระบุว่าโมเดลพบการหักล้างวันที่ 16 ตุลาคม และตรวจด้วย Lean วันที่ 17 ตุลาคม นักวิทยาศาสตร์ผู้ตรวจสอบไม่ได้ลงนามข้อตกลงรักษาความลับและไม่ได้รับค่าตอบแทน และขอให้ OpenAI เปิดเผยข้อมูลดิบทั้งหมดและสนับสนุนการประชุม ซึ่ง OpenAI ตกลง TechCrunch: ทั้งสองแล็บอ้างอัลกอริทึมที่แก้ปริศนาตรรกะยากเหล่านี้ได้ในเวลาต่ำกว่าเลขชี้กำลัง วิลเลียมส์บอกว่าบางส่วนดูเป็นเรื่องปกติ แต่ “สองสามส่วน” ดูแปลกประหลาดและต้องอาศัยแรงของวงการ เขาบอกว่านักวิทยาศาสตร์ควรให้น้ำหนักกับ P = NP มากขึ้นบ้าง สงสัยว่าอัลกอริทึมของ OpenAI ยังไม่ใช่วิธีที่ดีที่สุด และถามว่ามันทำลายการเข้ารหัสหรือไม่ ซึ่ง OpenAI ตอบว่า “ค่อนข้างมั่นใจ” ว่าไม่ งานวิจัยจำนวนมากที่อาศัย ETH อาจต้องทบทวนใหม่ถ้าข้ออ้างเป็นจริง
การหักล้าง ETH แสดงเพียงว่า 3-SAT มีอัลกอริทึมเวลาต่ำกว่าเลขชี้กำลัง ซึ่งไม่จำเป็นต้องเป็นพหุนาม คำถาม P กับ NP จึงยังไม่ได้คำตอบจากผลนี้ การหักล้างของ Anthropic รายงานโดย TechCrunch ภาพยนตร์นี้ไม่พบแถลงการณ์ของ Anthropic ที่อ้างอิงได้โดยตรง
ข้ออ้างปี 2026 ยังไม่ได้รับการยืนยัน ณ เวลาที่ทำภาพยนตร์นี้ ผู้เชี่ยวชาญอิสระยังตรวจสอบอยู่
แหล่งข้อมูล:
The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination) ;
TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean? บทส่งท้าย การตรวจนั้นง่าย การหาดูเหมือนยาก เจ็ดสิบปีมาแล้วที่ยังไม่มีใครพิสูจน์ได้ว่าช่องว่างนี้เป็นกฎของธรรมชาติ หรือเป็นแค่ความคิดที่เรายังหาไม่เจอ
เดือนนี้ เครื่องจักรเข้าร่วมการค้นหา บทพิสูจน์ของพวกมันจะรอดหรือไม่ กำลังถูกตัดสินด้วยวิธีที่คำถามนี้ทำนายไว้ คือการตรวจ ซึ่งเป็นส่วนที่ง่าย ทีละขั้นอย่างระมัดระวัง
1956 จดหมายของเกอเดิล1965 เอ็ดมอนด์ส: มีประสิทธิภาพ = พหุนาม1971 คุก: SAT เป็น NP-complete1972 21 ปัญหาของคาร์ป2000 รางวัล 1 ล้านดอลลาร์ของเคลย์2026 ข้ออ้างของ AI ต่อ ETH อยู่ระหว่างตรวจสอบP กับ NP ในหกวันที่ เจ็ดสิบปีต่อมา เกอเดิลตั้งคำถามนี้ในปี 1956 และรางวัลของเคลย์สำหรับคำตอบยังไม่มีใครได้รับตั้งแต่ปี 2000 ภาพประกอบสร้างด้วย AIภาพนิ่งและภาพประกอบสร้างด้วย AI ฉากต่าง ๆ เป็นแบบจำลองเพื่อการสอน ข้ออ้างปี 2026 ยังไม่ได้รับการยืนยัน เกี่ยวกับภาพยนตร์นี้
