# P กับ NP: ตรวจง่าย แต่หายาก > การตรวจซูโดกุที่เติมเสร็จแล้วใช้เวลาแค่นาทีเดียว แต่การหาคำตอบอาจนานกว่านั้นมาก ช่องว่างนี้มีอยู่จริง หรือเราแค่ยังหาเคล็ดลับไม่เจอ นี่คือหนึ่งในคำถามใหญ่ที่ยังไม่มีคำตอบของคณิตศาสตร์ มีรางวัลหนึ่งล้านดอลลาร์ และสัปดาห์นี้แล็บ AI อ้างว่าล้มข้อสันนิษฐานหนึ่งที่สร้างขึ้นรอบคำถามนี้ได้ Interactive film: https://www.planetpast.com/stories/p-vs-np-problem/?lang=th Publisher: PlanetPast (https://www.planetpast.com/) · d => T('readPublished', l, { d: dateIn(d, l) }) 2026-10-28 · Math, Technology ## บทนำ ### ตรวจง่าย แต่หายาก *คณิตศาสตร์ · เทคโนโลยี* หรือไม่ใช่? คำถามล้านดอลลาร์ วันที่ 26 ตุลาคม 2026 OpenAI ประกาศว่าโมเดล AI ของตนล้มข้อสันนิษฐานที่คนเชื่อกันกว้างขวาง ว่าปริศนาตรรกะบางแบบยากแค่ไหน ไม่กี่ชั่วโมงต่อมา Anthropic ก็บอกว่าโมเดลของตนทำได้เหมือนกัน งานวิจัยหลายร้อยชิ้นตั้งอยู่บนข้อสันนิษฐานนั้น นักวิทยาการคอมพิวเตอร์ชั้นนำจึงกำลังตรวจสอบทั้งสองข้ออ้างอย่างเปิดเผย และยังไม่มีใครยืนยัน จะเข้าใจว่าทำไมเรื่องนี้สำคัญ ต้องเริ่มจากปริศนาง่าย ๆ และคำถามที่มีค่าหนึ่งล้านดอลลาร์ - **ETH**: สมมติฐานเวลาเลขชี้กำลัง เสนอในปี 1999 - **หลายร้อย**: งานวิจัยวิทยาการคอมพิวเตอร์ที่อาศัยมัน (TNW) > “การเข้าร่วมของเราไม่ควรถูกตีความว่าเป็นการรับรองข้ออ้างนี้” (จดหมายเปิดผนึกของนักวิทยาการคอมพิวเตอร์ผู้ตรวจสอบ ผ่าน The Next Web) - ทำไมการตรวจจึงง่ายกว่าการหา - อัลกอริทึมเร็วและช้า - P, NP และ NP-complete - ข้ออ้างใหม่จะเปลี่ยนอะไร บทนำ #### ข้ออ้างที่กำลังถูกตรวจสอบ The Next Web (26 ต.ค. 2026): OpenAI ประกาศว่าโมเดลภายในของตนหักล้างสมมติฐานเวลาเลขชี้กำลังได้ ซึ่ง OpenAI เองบรรยายว่าเป็นข้อที่ “เชื่อกันกว้างขวางว่าเป็นจริง” บริษัทระบุว่าโมเดลพบการหักล้างวันที่ 16 ตุลาคม ตรวจด้วยโปรแกรมตรวจบทพิสูจน์ Lean วันที่ 17 ตุลาคม และเผยแพร่เอกสารกับบทพิสูจน์ใน GitHub รัสเซลล์ อิมพากลิอัซโซ และรามาโมฮัน ปาตูรี (UC San Diego) กับไรอัน วิลเลียมส์ (MIT) นำการตรวจสอบอิสระแบบเปิด จดหมายของพวกเขาระบุว่า “การเข้าร่วมของเราไม่ควรถูกตีความว่าเป็นการรับรองข้ออ้างนี้” และ “ถ้าข้ออ้างถูกต้อง มันจะเปลี่ยนส่วนสำคัญของวิทยาการคอมพิวเตอร์เชิงทฤษฎี” TechCrunch (27 ต.ค. 2026): ไม่กี่ชั่วโมงหลังนักคณิตศาสตร์ของ Anthropic ตั้งข้อสังเกตว่างานของ OpenAI อาศัยผลงานเดิม Anthropic ก็เผยแพร่การหักล้างของตนเองใน GitHub ข้ออ้างปี 2026 ยังไม่ได้รับการยืนยัน ณ เวลาที่ทำภาพยนตร์นี้ ผู้เชี่ยวชาญอิสระยังตรวจสอบอยู่ สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/) ## บทที่ I · ตรวจกับหา ### ตรวจกับหา *บทที่ I* อย่างหนึ่งเร็ว อีกอย่างอาจไม่เร็ว นี่คือซูโดกุที่เติมเสร็จแล้ว การตรวจทำได้แค่ไล่ดูแต่ละแถว แต่ละคอลัมน์ และแต่ละช่องใหญ่ว่ามีเลขซ้ำไหม ใช้เวลาแค่นาทีเดียว แต่การหาคำตอบจากตารางที่เกือบว่างเป็นอีกเรื่องหนึ่ง เราลองใส่เลข ถอยกลับ แล้วลองใหม่ และยิ่งตารางใหญ่ขึ้น ความเป็นไปได้ก็ยิ่งเพิ่มขึ้นแบบก้าวกระโดด การตรวจนั้นง่าย การหาดูเหมือนจะยาก ภาพยนตร์ทั้งเรื่องนี้คือคำถามว่าความต่างนั้นมีอยู่จริงหรือไม่ - 9 แถว: ไม่มีเลขซ้ำ - 9 คอลัมน์: ไม่มีเลขซ้ำ - 9 ช่องใหญ่: ไม่มีเลขซ้ำ - กดปุ่ม “ตรวจ” ในฉาก ![ดินสอเหนือตารางปริศนา สำหรับซูโดกุทั่วไปขนาด n² × n² การหาคำตอบเป็นปัญหา NP-complete (Fortnow, 2009) ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/88/881817b7bc8339ca.jpg) - **ตรวจ**: ไล่ตารางรอบเดียว - **หา**: อาจต้องค้นตัวเลือกนับไม่ถ้วน บทที่ I · ตรวจกับหา #### ตรวจง่าย Lance Fortnow, Communications of the ACM (2009): การแก้ซูโดกุขนาด n² × n² เป็นปัญหา NP-complete เช่นเดียวกับปัญหาคลิก (clique) การระบายสามสี และวงจรแฮมิลตัน ส่วนการตรวจคำตอบที่เสนอมาใช้แค่การไล่แถว คอลัมน์ และช่องใหญ่รอบเดียว TechCrunch (27 ต.ค. 2026) ใช้ตัวอย่างเดียวกัน: คำตอบซูโดกุตรวจง่ายแต่หายาก ลองดู: กดตรวจตาราง แล้วทำให้ผิดโดยสลับสองช่องแล้วตรวจอีกครั้ง ซูโดกุ 9 × 9 ทั่วไปเล็กพอที่คอมพิวเตอร์แก้ได้เร็ว ความยากอยู่ที่งานเพิ่มขึ้นอย่างไรเมื่อตารางใหญ่ขึ้น สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/) ### สถาบันคณิตศาสตร์เคลย์ยกอีกตัวอย่างหนึ่ง 13,717,421 เป็นผลคูณของจำนวนที่เล็กกว่าสองจำนวนหรือไม่ การหาด้วยมืออาจใช้เวลานานมาก แต่ถ้ามีคนบอกคำตอบว่า 3,607 คูณ 3,803 เราจะตรวจได้ด้วยเครื่องคิดเลขในไม่กี่วินาที ปัญหาในชีวิตจริงหลายอย่างมีรูปแบบนี้ คำตอบที่ดีอาจหายาก แต่พอเห็นแล้วก็รู้ได้ทันที ![เครื่องคิดเลขกลไกรุ่นเก่า ถ้าลองหารทีละตัว จะไปถึง 3,607 ได้หลังลองจำนวนเฉพาะไปแล้วหลายร้อยตัว ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/3b/3b8aee305699a2af.jpg) $$3607 \times 3803 = 13\,717\,421$$ - $3607,\ 3803$: ตัวประกอบสองตัว: หายาก แต่ตรวจง่าย - เส้นทางส่งของที่ไม่เกินระยะทางที่กำหนด - ตารางเวลาที่ไม่ชนกัน - การจัดของให้ไม่เกินน้ำหนักที่กำหนด บทที่ I · ตรวจกับหา #### หายาก แต่ตรวจง่าย สถาบันคณิตศาสตร์เคลย์ (คำอธิบายปัญหา): การหาสองจำนวนที่คูณกันได้ 13,717,421 เป็นเรื่องยาก แต่ใครก็ตรวจด้วยเครื่องคิดเลขได้ว่า 3,607 × 3,803 = 13,717,421 สถาบันยังยกตัวอย่างงานเลี้ยง การตรวจว่าเรารู้จักใครในงานทำได้เร็ว แต่การหาคนคนนั้นเองอาจต้องไล่ดูแขกทุกคน ลองดู: คูณตัวประกอบสองตัว แล้วลองแยกตัวประกอบด้วยการหารทีละตัว ดูตัวนับ ตัวอย่างเส้นทาง ตารางเวลา และการจัดของ เป็นรูปแบบหนึ่งของปัญหาพนักงานขายเดินทาง การจัดตาราง และปัญหาเป้ (knapsack) ซึ่งล้วนอยู่ใน NP (Britannica; Karp, 1972) สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Clay Mathematics Institute problem description of P vs NP (mirror): the party and factoring examples](https://www.mi.sanu.ac.rs/~zorano/izazovi21vek/p_vs_np.html); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems) ## บทที่ II · เร็วกับช้า ### เร็วกับช้า *บทที่ II* งานเพิ่มขึ้นอย่างไร คือตัวตัดสินทุกอย่าง นักวิทยาการคอมพิวเตอร์ตัดสินอัลกอริทึมจากว่าเวลาทำงานเพิ่มขึ้นอย่างไรเมื่อโจทย์ใหญ่ขึ้น ถ้าข้อมูลมี n ส่วน วิธีที่เร็วอาจใช้ราว n กำลังสองขั้น ปี 1965 แจ็ก เอ็ดมอนด์ส เสนอว่าอัลกอริทึมที่ดีคืออัลกอริทึมที่จำนวนขั้นไม่เกินพหุนามที่ตายตัวของขนาดข้อมูล เช่น n กำลังสอง หรือ n กำลังสาม วิธีแบบเลขชี้กำลังต่างออกไป จำนวนขั้นเพิ่มแบบสองยกกำลัง n คือทุกส่วนที่เพิ่มขึ้นหนึ่งส่วน งานจะเพิ่มเป็นสองเท่า เมื่อ n เท่ากับสิบ n กำลังสองคือหนึ่งร้อย และสองยกกำลัง n ราวหนึ่งพัน แต่เมื่อ n เท่ากับหนึ่งร้อย n กำลังสองคือหนึ่งหมื่น ขณะที่สองยกกำลัง n เป็นจำนวนที่มีสามสิบเอ็ดหลัก $$n^2 \quad \text{(polynomial)}$$ $$2^n \quad \text{(exponential)}$$ - $n$: ขนาดของข้อมูล - **“Paths, trees, and flowers”**: บทความที่มีอัลกอริทึมเร็วสำหรับการจับคู่ - **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³⁰ บทที่ II · เร็วกับช้า #### พหุนามกับเลขชี้กำลัง Britannica: P คือคลาสของปัญหาที่จำนวนขั้นไม่เกินพหุนามของความยาวข้อมูล n ซึ่งถือว่าง่ายหรือจัดการได้ (tractable) Fortnow (2009) และ Sipser (1992): ในบทความ “Paths, trees, and flowers” (1965) แจ็ก เอ็ดมอนด์ส ให้อัลกอริทึมเวลาพหุนามสำหรับปัญหาการจับคู่ และเสนอว่าการคำนวณที่มีประสิทธิภาพคือเวลาที่ไม่เกินพหุนามที่ตายตัวของขนาดข้อมูล ซึ่งต่อมากลายเป็นคลาส P ตัวเลขเป็นเลขคณิต: 10² = 100, 2¹⁰ = 1,024, 100² = 10,000 และ 2¹⁰⁰ ≈ 1.27 × 10³⁰ ซึ่งมี 31 หลัก ลองดู: เปลี่ยนค่า n แล้วเทียบแท่ง แท่งวาดด้วยสเกลลอการิทึม (ความสูงคือจำนวนหลัก) ไม่อย่างนั้น 2ⁿ จะทะลุจอ สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf) ### นี่คือปริศนาแบบที่อยู่ใจกลางข่าว สูตรตรรกะมีสวิตช์ n ตัว แต่ละตัวเป็นจริงหรือเท็จ พร้อมรายการกฎเกี่ยวกับมัน มีวิธีตั้งสวิตช์ที่ทำตามกฎได้ทุกข้อหรือไม่ นี่เรียกว่าปัญหาการทำให้สูตรเป็นจริงได้ (satisfiability) หรือ SAT การตรวจวิธีตั้งที่เสนอมาทำได้เร็ว แค่ไล่ดูกฎทีละข้อ แต่วิธีหาที่ตรงไปตรงมาที่สุดคือลองทุกแบบ และสวิตช์ n ตัวมีวิธีตั้งสองยกกำลัง n แบบ เพิ่มสวิตช์สิบตัว ก็ต้องลองมากขึ้นราวหนึ่งพันเท่า - สวิตช์ n ตัว: จริงหรือเท็จ - กฎเช่น “A หรือ ไม่ใช่ B หรือ C” - เป้าหมาย: ทำตามกฎทุกข้อพร้อมกัน ![แผงสวิตช์โยกรุ่นเก่า ถ้ามี 30 สวิตช์ ก็มีวิธีตั้งราว 1.07 พันล้านแบบแล้ว ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/7e/7e411a1c1ccc1093.jpg) - **1,024**: n = 10 - **≈ 1.07 พันล้าน**: n = 30 - **≈ 1.27 × 10³⁰**: n = 100 $$2^{n+10} = 1024 \times 2^{n}$$ - $+10$: สวิตช์เพิ่มสิบตัว บทที่ II · เร็วกับช้า #### ปัญหาความสอดคล้องได้ Impagliazzo & Paturi: ปัญหา k-SAT ถามว่าสูตรรูป k-CNF (กฎหลายข้อเชื่อมด้วย “และ” แต่ละข้อคือสวิตช์ k ตัวหรือนิเสธของมันเชื่อมด้วย “หรือ”) มีวิธีตั้งค่าที่ทำให้เป็นจริงหรือไม่ การลองทุกแบบต้องลองวิธีตั้ง 2ⁿ แบบสำหรับตัวแปร n ตัว Britannica: การตรวจคำตอบที่เสนอมาของปัญหา NP ใช้เวลาพหุนาม ลองดู: สุ่มโยกสวิตช์ หรือสั่งค้นแบบลองทุกแบบแล้วดูตัวนับเทียบกับ 2ⁿ ฉากนี้ใช้ 12 สวิตช์ (4,096 แบบ) อัลกอริทึมที่ฉลาดกว่าทำได้ดีกว่าการลองทุกแบบ แต่ทุกอัลกอริทึมที่รู้จักก่อนข้ออ้างเดือนตุลาคม 2026 ยังใช้เวลาแบบเลขชี้กำลัง (Institute for Advanced Study) สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Institute for Advanced Study: Do NP-hard problems require exponential time?](https://ias.edu/node/74266) ## บทที่ III · คำถาม ### คำถาม *บทที่ III* ทุกอย่างที่ตรวจได้เร็ว หาได้เร็วด้วยไหม ทีนี้มาดูสองตระกูล P คือกลุ่มปัญหาที่แก้ได้ในเวลาพหุนาม หรือปัญหาที่เรานับว่าจัดการได้ NP คือกลุ่มปัญหาที่คำตอบที่เสนอมาตรวจสอบได้ในเวลาพหุนาม ซูโดกุ SAT และปริศนาการแยกตัวประกอบล้วนอยู่ใน NP ทุกปัญหาใน P อยู่ใน NP ด้วย ถ้าหาคำตอบได้เร็ว ก็ย่อมตรวจได้เร็วแน่นอน คำถามที่ยังเปิดอยู่คือทิศทางกลับกัน ถ้าทุกปัญหาที่ตรวจได้เร็วแก้ได้เร็วด้วย ก็แปลว่า P เท่ากับ NP นักวิจัยส่วนใหญ่คิดว่าไม่ใช่ แต่ยังไม่มีใครพิสูจน์ได้ทั้งสองทาง - แก้ได้ในเวลาพหุนาม - ตัวอย่าง: เรียงลำดับรายการ - ตัวอย่าง: หาเส้นทางที่สั้นที่สุด - ตรวจคำตอบได้ในเวลาพหุนาม - รวม P ทั้งหมดไว้ - รวม SAT ซูโดกุ และการแยกตัวประกอบ - NP ย่อมาจาก “nondeterministic polynomial time” ไม่ได้แปลว่า “ไม่ใช่พหุนาม” $$\mathrm{P} \subseteq \mathrm{NP}$$ $$\mathrm{P} \overset{?}{=} \mathrm{NP}$$ - $\subseteq$: “อยู่ภายใน” - **ยังเปิดอยู่**: ยังไม่มีบทพิสูจน์ทั้งสองทาง - **1 ล้านดอลลาร์**: รางวัลของเคลย์สำหรับบทพิสูจน์ที่ถูกต้อง บทที่ III · คำถาม #### P และ NP Britannica: P คือปัญหาที่จำนวนขั้นไม่เกินพหุนามของ n ส่วน NP คือปัญหาที่ตรวจคำตอบที่เดามาได้ในเวลาพหุนาม P เป็นสับเซตของ NP คำถามคือ P เท่ากับ NP หรือไม่ นั่นคือ ทุกปัญหาที่ตรวจคำตอบได้เร็วจะแก้ได้เร็วด้วยหรือไม่ TechCrunch: นักวิจัยส่วนใหญ่สันนิษฐานว่า P ≠ NP การเรียงลำดับและการหาเส้นทางที่สั้นที่สุดเป็นตัวอย่างในตำราของปัญหาที่มีอัลกอริทึมเวลาพหุนาม วงในฉากแสดงคลาสตามที่นักวิจัยส่วนใหญ่เชื่อ ถ้า P = NP วงในจะขยายเต็มวงนอก สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/) ### คำถามนี้เก่ากว่าคอมพิวเตอร์ส่วนใหญ่ ปี 1956 นักตรรกศาสตร์ เคิร์ท เกอเดิล เขียนจดหมายถึงจอห์น ฟอน นอยมันน์ ซึ่งกำลังป่วยหนักใกล้เสียชีวิต เขาถามว่างานของเครื่องจักรจะเพิ่มเร็วแค่ไหน ถ้าต้องตัดสินว่าข้อความหนึ่งมีบทพิสูจน์ที่ยาวตามที่กำหนดหรือไม่ ถ้างานเพิ่มช้า เขาเขียนว่า ความพยายามทางความคิดของนักคณิตศาสตร์กับคำถามแบบใช่หรือไม่ใช่จะถูกแทนด้วยเครื่องจักรได้ และจะมีผลตามมามหาศาลที่สุด ![จดหมายและปากกาหมึกซึมยุค 1950 ต้นฉบับจดหมายของเกอเดิลเก็บไว้ที่หอสมุดรัฐสภาสหรัฐฯ (Sipser) ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/2d/2de607e037658300.jpg) > “…ผลตามมาที่มหาศาลที่สุด” (เคิร์ท เกอเดิล ถึงจอห์น ฟอน นอยมันน์ ปี 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)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf); [Wikipedia: P versus NP problem (consequences)](https://en.wikipedia.org/wiki/P_versus_NP_problem) ## บทที่ IV · ได้หมดหรือไม่ได้เลย ### ได้หมดหรือไม่ได้เลย *บทที่ IV* ปัญหามากมาย ชะตาเดียวกัน ปี 1971 สตีเฟน คุก พิสูจน์สิ่งที่น่าทึ่ง ทุกปัญหาใน NP แปลงเป็น SAT หรือปริศนาสวิตช์ได้อย่างรวดเร็ว ดังนั้นถ้ามีวิธีแก้ SAT ได้เร็ว ก็จะมีวิธีแก้ทุกปัญหาใน NP ได้เร็วด้วย ปัญหาที่มีคุณสมบัตินี้เรียกว่า NP-complete และ SAT คือปัญหาแรก ลีโอนิด เลวิน ค้นพบแนวคิดเดียวกันอย่างอิสระและตีพิมพ์ในปี 1973 ต่อมาคุกได้รับรางวัลทัวริงจากงานนี้ ซึ่งมักถูกเรียกว่ารางวัลโนเบลของวงการคอมพิวเตอร์ - **1971**: คุก ในการประชุม ACM STOC - **1973**: เลวิน อย่างอิสระ - อยู่ใน NP - ทุกปัญหา NP แปลงมาเป็นมันได้เร็ว - แก้มันได้เร็ว ก็แก้ NP ทั้งหมดได้เร็ว ![ถ้วยรางวัลเรียบ ๆ บนโต๊ะที่มีกองกระดาษ คุกได้รับรางวัลทัวริงในปี 1982 ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/98/989033725b0aeb92.jpg) บทที่ 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)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem) ### ปีต่อมา ริชาร์ด คาร์ป แสดงว่าปัญหาที่รู้จักกันดียี่สิบเอ็ดปัญหาเป็น NP-complete ด้วย รวมถึงการระบายสีเครือข่าย การหาเส้นทางวนที่ผ่านทุกจุดเพียงครั้งเดียว และการจัดของใส่เป้ หลังจากนั้นมีปัญหาอีกมากเข้ามาร่วมรายการ ทั้งปัญหาพนักงานขายเดินทางและซูโดกุตารางใหญ่ พวกมันจะง่ายหรือยากไปพร้อมกัน ถ้าหาวิธีที่เร็วสำหรับปัญหาใดปัญหาหนึ่งได้ ก็จะมีวิธีสำหรับทุกปัญหา และ P เท่ากับ NP ถ้าพิสูจน์ได้ว่าปัญหาใดปัญหาหนึ่งไม่มีวิธีที่เร็ว P ก็ไม่เท่ากับ NP ลองระบายสีเครือข่ายนี้ด้วยสามสี โดยจุดที่เชื่อมกันต้องไม่เป็นสีเดียวกัน การตรวจทำได้ทันที แต่การหาอาจต้องใช้เวลา - จำนวนสีน้อยที่สุด (chromatic number) - วงจรแฮมิลตัน - ปัญหาเป้ (knapsack) - คลิก (clique) 3-SAT และอื่น ๆ ![หมุดและด้ายบนแผนที่เก่าที่ลากเป็นเส้นทาง การตรวจว่าเส้นทางที่ให้มาไม่เกินระยะทางที่กำหนดทำได้เร็ว ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/97/97d19d2d6eb1ae69.jpg) - **ข้อใดข้อหนึ่งเร็ว**: → เร็วทั้งหมด: P = NP - **พิสูจน์ได้ว่าข้อหนึ่งช้า**: → P ≠ NP - **19**: จุด - **3**: สีที่ใช้ได้ - **3¹⁹**: วิธีระบายที่เป็นไปได้: ราว 1.16 พันล้าน บทที่ IV · ได้หมดหรือไม่ได้เลย #### ยี่สิบเอ็ดปัญหา แล้วก็อีกมากมาย ริชาร์ด คาร์ป “Reducibility Among Combinatorial Problems” (1972) แสดงว่า 21 ปัญหาเป็น NP-complete รวมถึง SAT, 3-SAT, จำนวนสี (การระบายสีกราฟ), คลิก (clique), วงจรแฮมิลตัน และปัญหาเป้ (ACM; Wikipedia) Britannica ระบุว่าปัญหาพนักงานขายเดินทางและ SAT เป็น NP-complete Fortnow (2009) เพิ่มการระบายสามสีและซูโดกุขนาด n² × n² Britannica: อัลกอริทึมที่มีประสิทธิภาพสำหรับปัญหา NP-complete ใดปัญหาหนึ่ง จะให้อัลกอริทึมที่มีประสิทธิภาพสำหรับทุกปัญหาใน NP ลองดู: สุ่มระบายสีแล้วตรวจ (เส้นที่ชนกันจะเป็นสีแดง) หรือให้คอมพิวเตอร์ค้นหา ซึ่งลองสีทีละจุดและถอยกลับเมื่อติด เครือข่ายเล็ก ๆ นี้แก้ได้เร็ว ความยากอยู่ที่การค้นหาโตขึ้นตามขนาด สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [ACM A.M. Turing Award: Stephen A. Cook (1982)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf) ## บทที่ V · ทำไมจึงสำคัญ ### ทำไมจึงสำคัญ *บทที่ V* รางวัล และแม่กุญแจของอินเทอร์เน็ต ปี 2000 สถาบันคณิตศาสตร์เคลย์จัดให้ปัญหา P กับ NP เป็นหนึ่งในเจ็ดปัญหารางวัลมิลเลนเนียม มีรางวัลหนึ่งล้านดอลลาร์สำหรับผู้ไขได้ ในเจ็ดปัญหานั้น มีเพียงข้อความคาดการณ์ของปวงกาเรข้อเดียวที่ถูกไขแล้ว เดิมพันนี้ยังเป็นเรื่องในชีวิตจริงด้วย การเข้ารหัสยุคใหม่จำนวนมากตั้งอยู่บนความเชื่อว่าปัญหาบางอย่าง เช่น การแยกตัวประกอบผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัว แก้ได้เร็วไม่ได้ การแยกตัวประกอบอยู่ใน NP แต่ไม่เชื่อกันว่าเป็น NP-complete ดังนั้นแม้จะพิสูจน์ได้ว่า P ไม่เท่ากับ NP ก็ยังไม่ได้พิสูจน์ว่าการแยกตัวประกอบยาก ทิศทางกลับกันชัดเจนกว่า อย่างที่นักวิทยาการคอมพิวเตอร์ แลนซ์ ฟอร์ตนาว กล่าวไว้ ถ้า P เท่ากับ NP การเข้ารหัสแบบกุญแจสาธารณะจะเป็นไปไม่ได้ - **7**: ปัญหา ประกาศ 24 พฤษภาคม 2000 ที่ปารีส - **1 ล้านดอลลาร์**: ต่อปัญหา - **1**: ที่ไขได้แล้ว: ปวงกาเร ![แม่กุญแจบนตู้เซิร์ฟเวอร์ Britannica: การเข้ารหัสยุคใหม่อาศัยข้อสันนิษฐานว่าการแยกตัวประกอบไม่อยู่ใน P ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/f2/f21e9c5af24aa559.jpg) - อยู่ใน 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](https://www.claymath.org/millennium-problems); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf) ### ถ้า P เท่ากับ NP จริง และวิธีนั้นใช้ได้จริงในทางปฏิบัติ ปัญหาการวางแผนยาก ๆ จำนวนมากจะกลายเป็นเรื่องง่าย และคอมพิวเตอร์จะค้นหาบทพิสูจน์ของทฤษฎีบทได้ อย่างที่คุกเองเคยชี้ไว้ ผู้เชี่ยวชาญส่วนใหญ่ไม่เชื่อ ในการสำรวจนักวิจัย 124 คนของวิลเลียม แกสาร์ช ปี 2019 แปดสิบแปดเปอร์เซ็นต์เชื่อว่า P ไม่เท่ากับ NP และสิบสองเปอร์เซ็นต์เชื่อว่าเท่ากัน แต่การสำรวจความเห็นไม่ใช่บทพิสูจน์ และข้ออ้างเดือนนี้ก็แสดงว่าแม้ความเชื่อที่คนส่วนใหญ่ยึดถือก็ถูกทดสอบได้ ลองดูทั้งสองโลก - ปัญหาเส้นทางและโลจิสติกส์แก้ได้อย่างมีประสิทธิภาพ - คอมพิวเตอร์หาบทพิสูจน์ที่ยาวพอสมควรได้ - การค้นหาในงานออกแบบและจัดตารางจำนวนมากจะเร็วขึ้น - 2002: 61% - 2012: 83% - 2019: 88% - 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)](https://en.wikipedia.org/wiki/P_versus_NP_problem); [William Gasarch (2019): The third P =? NP poll](https://www.cs.umd.edu/users/gasarch/papers/poll3.pdf); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf) ## บทที่ VI · ข้ออ้างใหม่ ### ข้ออ้างใหม่ *บทที่ VI* เดิมพันที่หนักกว่า และเครื่องจักรที่ท้าทายมัน สมมติฐานเวลาเลขชี้กำลังไปไกลกว่าคำถาม P กับ NP รัสเซลล์ อิมพากลิอัซโซ และรามาโมฮัน ปาตูรี วางมันไว้ในปี 1999 ว่า 3-SAT ซึ่งคือปริศนาสวิตช์ที่แต่ละกฎมีสวิตช์สามตัว แก้ในเวลาต่ำกว่าเลขชี้กำลังไม่ได้ พูดอีกอย่างคือ ทุกวิธีต้องใช้เวลาที่เพิ่มอย่างน้อยแบบสองยกกำลังเศษส่วนคงที่ของ n ซึ่งยังคงเพิ่มเป็นเท่าตัวในอัตราคงที่ วิธีที่ต่ำกว่าเลขชี้กำลังจะเพิ่มช้ากว่าทุกเส้นเหล่านั้น แต่ไม่จำเป็นต้องช้าเท่าพหุนาม มันเป็นเดิมพันที่หนักกว่า P ไม่เท่ากับ NP เพราะถ้ามันจริง P ก็ไม่เท่ากับ NP ลองกดปุ่มเทียบเส้นโค้ง งานวิจัยวิทยาการคอมพิวเตอร์หลายร้อยชิ้นตั้งอยู่บนสมมติฐานนี้ โดยใช้มันแสดงว่าปัญหาอื่นแก้ได้เร็วแค่ไหน และเร็วกว่านั้นไม่ได้ $$\exists\, \delta > 0:\ \text{3-SAT needs } 2^{\delta n} \text{ time}$$ - $\delta$: เศษส่วนบวกคงที่ค่าหนึ่ง - $n$: จำนวนสวิตช์ (ตัวแปร) $$2^{n},\ 2^{n/10} \quad \text{exponential}$$ $$2^{\sqrt{n}} \quad \text{sub-exponential}$$ $$n^{3} \quad \text{polynomial}$$ - $2^{\sqrt{n}}$: ตัวอย่างในตำรา ไม่ใช่อัลกอริทึมที่ถูกอ้าง - ETH จริง → P ≠ NP จริง - ETH เท็จ → P กับ NP ยังเปิดอยู่ - ETH เป็นข้อความที่เข้มกว่า P ≠ NP (MIT) - **หลายร้อย**: งานวิจัยวิทยาการคอมพิวเตอร์ - **1999**: อิมพากลิอัซโซและปาตูรีเผยแพร่ครั้งแรก บทที่ VI · ข้ออ้างใหม่ #### สมมติฐานเวลาเลขชี้กำลัง Impagliazzo & Paturi: ให้ s_k คือค่า δ ที่เล็กที่สุดที่ k-SAT มีอัลกอริทึม O(2^{δn}) สมมติฐานเวลาเลขชี้กำลังระบุว่า s_k > 0 เมื่อ k ≥ 3 “พูดอีกอย่างคือ เมื่อ k ≥ 3 ปัญหา k-SAT ไม่มีอัลกอริทึมเวลาต่ำกว่าเลขชี้กำลัง” TechCrunch: อิมพากลิอัซโซและปาตูรีเผยแพร่ ETH ครั้งแรกในปี 1999 บันทึกการสอนของ MIT (V. Vassilevska Williams): ETH ระบุว่ามี δ > 0 ที่ทำให้ 3-SAT ต้องใช้เวลา 2^{δn} ซึ่งเป็น “การทำให้ P ≠ NP แข็งขึ้น” The Next Web: งานวิจัยวิทยาการคอมพิวเตอร์หลายร้อยชิ้นตั้งอยู่บน ETH แถบสีส้มในฉากคือกลุ่มเส้นโค้ง 2^{δn} ETH บอกว่า 3-SAT อยู่เหนือเส้นใดเส้นหนึ่งในนั้นเสมอ รูปทรงเป็นภาพประกอบ สวิตช์ ตาราง แผนที่ และแผนภาพเป็นแบบจำลองเพื่อการสอน จำนวนขั้นในฉากใช้แสดงการเติบโต ไม่ใช่เวลาของคอมพิวเตอร์จริง แหล่งข้อมูล: [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [MIT 6.S078 lecture notes (V. Vassilevska Williams): ETH as a strengthening of P ≠ NP](https://people.csail.mit.edu/virgi/6.s078/lect2.pdf); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/); [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills) ### OpenAI ระบุว่าโมเดลพบการหักล้างนี้วันที่ 16 ตุลาคม และวันถัดมาได้ตรวจด้วย Lean ซึ่งเป็นโปรแกรมตรวจบทพิสูจน์ทีละบรรทัด แล็บเหล่านี้อ้างว่ามีอัลกอริทึมที่แก้ปริศนาเหล่านี้ได้ในเวลาต่ำกว่าเลขชี้กำลัง อิมพากลิอัซโซ ปาตูรี และไรอัน วิลเลียมส์ แห่ง MIT นำการตรวจสอบแบบเปิด วิลเลียมส์บอกว่าบางส่วนของบทพิสูจน์ดูเป็นเรื่องปกติ แต่มีบางส่วนแปลกพอที่ต้องอาศัยแรงของทั้งวงการ OpenAI บอกว่าค่อนข้างมั่นใจว่าผลนี้ไม่ทำลายการเข้ารหัส และแม้มันจะถูกต้อง วิธีที่ต่ำกว่าเลขชี้กำลังก็ไม่ใช่วิธีแบบพหุนาม จึงยังไม่ได้แสดงว่า P เท่ากับ NP วิลเลียมส์บอกว่ามันควรทำให้ความเป็นไปได้นั้นมีน้ำหนักขึ้นเล็กน้อย แต่เขาสงสัยว่าอัลกอริทึมนี้ยังไม่ใช่วิธีที่ดีที่สุด - อัลกอริทึมเวลาต่ำกว่าเลขชี้กำลังสำหรับปริศนา SAT เหล่านี้ - บทพิสูจน์ตรวจด้วย Lean และเผยแพร่บน GitHub - ยังไม่ได้รับการยืนยันโดยอิสระ ![หน้ากระดาษพิมพ์และบันทึกบนโต๊ะสัมมนา ผู้ตรวจสอบขอให้ OpenAI เปิดเผยข้อมูลดิบทั้งหมดและสนับสนุนการประชุม ซึ่ง OpenAI ตกลง (TNW) ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/92/92844c4e4483e747.jpg) - ETH เป็นเท็จ - งานวิจัยที่สันนิษฐาน 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)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/) ## บทส่งท้าย ### การตรวจนั้นง่าย การหาดูเหมือนยาก เจ็ดสิบปีมาแล้วที่ยังไม่มีใครพิสูจน์ได้ว่าช่องว่างนี้เป็นกฎของธรรมชาติ หรือเป็นแค่ความคิดที่เรายังหาไม่เจอ เดือนนี้ เครื่องจักรเข้าร่วมการค้นหา บทพิสูจน์ของพวกมันจะรอดหรือไม่ กำลังถูกตัดสินด้วยวิธีที่คำถามนี้ทำนายไว้ คือการตรวจ ซึ่งเป็นส่วนที่ง่าย ทีละขั้นอย่างระมัดระวัง - 1956: จดหมายของเกอเดิล - 1965: เอ็ดมอนด์ส: มีประสิทธิภาพ = พหุนาม - 1971: คุก: SAT เป็น NP-complete - 1972: 21 ปัญหาของคาร์ป - 2000: รางวัล 1 ล้านดอลลาร์ของเคลย์ - 2026: ข้ออ้างของ AI ต่อ ETH อยู่ระหว่างตรวจสอบ ![เกอเดิลตั้งคำถามนี้ในปี 1956 และรางวัลของเคลย์สำหรับคำตอบยังไม่มีใครได้รับตั้งแต่ปี 2000 ภาพประกอบสร้างด้วย AI](https://assets.planetpast.com/a/2d/2de607e037658300.jpg) - ภาพนิ่งและภาพประกอบสร้างด้วย AI - ฉากต่าง ๆ เป็นแบบจำลองเพื่อการสอน - ข้ออ้างปี 2026 ยังไม่ได้รับการยืนยัน บทส่งท้าย · แหล่งข้อมูล #### แหล่งข้อมูล ข้อเท็จจริงทุกข้อในภาพยนตร์นี้มาจากแหล่งด้านล่าง ภาพนิ่งประจำบทและภาพประกอบสร้างด้วย AI ฉากต่าง ๆ เป็นแบบจำลองเพื่อการสอน ข้ออ้างเดือนตุลาคม 2026 ถูกนำเสนอในฐานะข้ออ้าง ณ เวลาที่ทำภาพยนตร์นี้ ผู้เชี่ยวชาญอิสระยังตรวจสอบอยู่ และผลการตรวจอาจเปลี่ยนสิ่งที่กล่าวในบทสุดท้าย แหล่งข้อมูล: [The Next Web (26 Oct 2026): OpenAI says its AI model has disproved the Exponential Time Hypothesis (dates, Lean check, the open examination)](https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills); [TechCrunch (27 Oct 2026): Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?](https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/); [Impagliazzo & Paturi: Complexity of k-SAT (the Exponential Time Hypothesis), UC San Diego](https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_1999_ccc.pdf); [MIT 6.S078 lecture notes (V. Vassilevska Williams): ETH as a strengthening of P ≠ NP](https://people.csail.mit.edu/virgi/6.s078/lect2.pdf); [Encyclopaedia Britannica: P versus NP problem](https://britannica.com/topic/P-versus-NP-problem); [Encyclopaedia Britannica: NP-complete problem](https://britannica.com/science/NP-complete-problem); [Clay Mathematics Institute: The Millennium Prize Problems](https://www.claymath.org/millennium-problems); [Clay Mathematics Institute problem description of P vs NP (mirror): the party and factoring examples](https://www.mi.sanu.ac.rs/~zorano/izazovi21vek/p_vs_np.html); [Lance Fortnow, Communications of the ACM (2009): The status of the P versus NP problem](https://courses.cs.duke.edu/fall20/compsci590.7/CACM-Fortnow.pdf); [Michael Sipser (1992): The history and status of the P versus NP question (Gödel’s 1956 letter, Edmonds)](https://www.cs.columbia.edu/~tal/3261/sipserpnp.pdf); [ACM A.M. Turing Award: Stephen A. Cook (1982)](https://amturing.acm.org/award_winners/cook_n991950.cfm); [Wikipedia: Karp’s 21 NP-complete problems](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems); [William Gasarch (2019): The third P =? NP poll](https://www.cs.umd.edu/users/gasarch/papers/poll3.pdf); [Wikipedia: P versus NP problem (consequences)](https://en.wikipedia.org/wiki/P_versus_NP_problem)