06 · The Wall
06 · กำแพง
THE SHORTEST PATH — A History of the Art and Science of Problem-Solving
เส้นทางที่สั้นที่สุด — ประวัติศาสตร์ของศิลปะและศาสตร์แห่งการแก้ปัญหา
A letter to a dying man
จดหมายถึงชายที่กำลังจะตาย
In the spring of 1956, John von Neumann was fifty-three years old and dying of cancer, confined increasingly to Walter Reed hospital, his once-astonishing productivity narrowing to whatever his failing body would allow. Kurt Gödel — his old friend from Vienna, the logician who had shattered Hilbert's dream of a complete and consistent mathematics twenty-five years earlier — wrote to him that March, and by most accounts the letter was partly an attempt to give a brilliant, dying mind something to chew on besides its own decline.
ฤดูใบไม้ผลิปี 1956 John von Neumann อายุห้าสิบสาม กำลังจะตายด้วยโรคมะเร็ง และถูกกักตัวอยู่ในโรงพยาบาล Walter Reed นานขึ้นทุกที ผลงานที่เคยไหลออกมาไม่หยุดหดเหลือเท่าที่ร่างกายที่กำลังทรุดจะยอมให้ทำ เดือนมีนาคมปีนั้น Kurt Gödel เขียนจดหมายถึงเขา Gödel คือเพื่อนเก่าจากเวียนนา นักตรรกวิทยาที่ทุบความฝันของ Hilbert เรื่องคณิตศาสตร์ที่ครบถ้วนและสอดคล้องในตัวเองจนแตกเมื่อยี่สิบห้าปีก่อน ตามคำบอกเล่าส่วนใหญ่ จดหมายฉบับนั้นส่วนหนึ่งเขียนขึ้นเพื่อหาอะไรให้สมองที่เฉียบแหลมและกำลังจะดับได้ขบคิด นอกเหนือไปจากความเสื่อมถอยของตัวมันเอง
The question Gödel posed was technical, almost casual in its phrasing, and it would take computer science another decade and a half to realize what he had actually asked. Consider a mathematical statement of a certain length. Checking whether a proposed proof of that statement is correct can obviously be done quickly — you just verify each step. But how long does it take to find a proof at all, if one exists? Gödel wanted to know whether this search could always be done in time roughly proportional to the length of the statement (or its square), rather than growing explosively as statements get longer. He was, in effect, asking whether finding is fundamentally harder than checking — the question that decades later would be given the name P versus NP (Cornell eCommons, "Gödel, von Neumann and the P=?NP Problem"; Panda Notes, "Gödel's Letter to von Neumann"). Von Neumann died the following February. Whether he ever replied is not known; no response survives. The question sat, essentially unnoticed outside a small circle, for fifteen more years.
คำถามของ Gödel เป็นคำถามเชิงเทคนิค เขียนเกือบเหมือนเอ่ยผ่านๆ และวิทยาการคอมพิวเตอร์ต้องใช้เวลาอีกสิบห้าปีกว่าจะรู้ตัวว่าเขาถามอะไรไปกันแน่ เอาข้อความทางคณิตศาสตร์ที่มีความยาวค่าหนึ่งมาตั้ง การตรวจว่าบทพิสูจน์ที่มีคนเสนอมาสำหรับข้อความนั้น*ถูกต้อง*หรือไม่ ทำได้เร็วอยู่แล้วอย่างเห็นได้ชัด — ตรวจสอบทีละก้าวก็จบ แต่ถ้าบทพิสูจน์มีอยู่ การ*หา*มันให้เจอตั้งแต่ต้นใช้เวลานานแค่ไหน Gödel อยากรู้ว่าการค้นหา (search) นี้ทำให้เสร็จได้เสมอไหมในเวลาที่แปรผันคร่าวๆ ตามความยาวของข้อความ (หรือกำลังสองของความยาวนั้น) แทนที่จะโตระเบิดเมื่อข้อความยาวขึ้น เอาเข้าจริงเขากำลังถามว่าการ*หา*ยากกว่าการ*ตรวจ*โดยพื้นฐานหรือเปล่า คำถามนี้อีกหลายทศวรรษต่อมาจะได้ชื่อว่า P versus NP (Cornell eCommons, "Gödel, von Neumann and the P=?NP Problem"; Panda Notes, "Gödel's Letter to von Neumann") Von Neumann เสียชีวิตในเดือนกุมภาพันธ์ปีถัดมา เขาเคยตอบหรือไม่ ไม่มีใครรู้; ไม่มีคำตอบหลงเหลือมาถึงเรา คำถามนี้นอนนิ่งอยู่อีกสิบห้าปี แทบไม่มีใครนอกวงเล็กๆ สังเกตเห็น
This chapter is about what happened when the question was finally answered — not solved, but given a precise shape and a name — and about the strange, double-edged discovery that followed: that some problems appear to resist every clever reframing this book has celebrated so far, and that this resistance, once proven, becomes a kind of knowledge in its own right.
บทนี้ว่าด้วยสิ่งที่เกิดขึ้นเมื่อคำถามนี้ได้คำตอบในที่สุด — ไม่ใช่ถูกแก้ แต่ได้รูปทรงที่ชัดเจนและได้ชื่อ — และว่าด้วยการค้นพบที่แปลกและมีคมสองด้านที่ตามมา ปัญหาบางข้อดูจะต้านทานการเปลี่ยนกรอบ (reframe) อันชาญฉลาด*ทุกแบบ*ที่หนังสือเล่มนี้ยกย่องมาจนถึงตอนนี้ และเมื่อพิสูจน์การต้านทานนั้นได้แล้ว มันก็กลายเป็นความรู้ชนิดหนึ่งในตัวมันเอง
One Disease, Many Symptoms
โรคเดียว อาการมากมาย
The formal birth of the field came in 1971, when Stephen Cook, then at the University of Toronto, published a short paper titled "The Complexity of Theorem-Proving Procedures." Cook studied the Boolean satisfiability problem, SAT: given a logical formula built from variables that can each be TRUE or FALSE, connected by ANDs, ORs, and NOTs, is there some assignment of values that makes the whole formula true? Checking a proposed assignment is trivial — plug in the values and evaluate. Finding one, when the formula has thousands of variables locked together by thousands of constraints, seemed to require something close to trying all possibilities.
สาขานี้ถือกำเนิดอย่างเป็นทางการในปี 1971 เมื่อ Stephen Cook ซึ่งตอนนั้นอยู่ที่ University of Toronto ตีพิมพ์บทความสั้นชื่อ "The Complexity of Theorem-Proving Procedures" Cook ศึกษาปัญหาความสอดคล้องได้แบบบูล (Boolean satisfiability) หรือ SAT: ให้สูตรตรรกะที่สร้างจากตัวแปรที่แต่ละตัวเป็น TRUE หรือ FALSE ได้ เชื่อมกันด้วย AND, OR และ NOT — มีการกำหนดค่า*ชุดใดชุดหนึ่ง*ที่ทำให้สูตรทั้งสูตรเป็นจริงหรือไม่ ตรวจการกำหนดค่าที่เสนอมานั้นง่ายมาก — แทนค่าลงไปแล้วประเมิน หาการกำหนดค่าสักชุดนั้นอีกเรื่อง เมื่อสูตรมีตัวแปรเป็นพันตัวที่ล็อกเข้าด้วยกันด้วยข้อจำกัดเป็นพันข้อ ดูจะต้องใช้อะไรที่ใกล้เคียงกับการลองทุกความเป็นไปได้
Cook's insight was not to solve SAT faster. It was to show that SAT is, in a precise sense, the hardest problem of its kind: any problem whose solutions can be quickly checked (this class is called NP, for "nondeterministic polynomial time") can be systematically translated — "reduced" — into an equivalent instance of SAT, using only a modest, efficient amount of computation to perform the translation. If you could solve SAT quickly, you could solve anything checkable-in-NP quickly, by first translating it into SAT. This property earned SAT the label NP-complete: complete, in the sense of capturing the full difficulty of the entire class (GeeksforGeeks, "Cook–Levin Theorem"). Working independently and in near-total isolation behind the Iron Curtain, the Soviet mathematician Leonid Levin arrived at essentially the same result at almost the same time, framed slightly differently, around 1973 — a discovery so cleanly convergent that the result now carries both names, the Cook–Levin theorem, an acknowledgment that important mathematical truths sometimes get discovered twice by people who have never read each other's work.
การหยั่งเห็น (insight) ของ Cook ไม่ใช่การแก้ SAT ให้เร็วขึ้น แต่คือการแสดงว่า SAT เป็นปัญหาที่*ยากที่สุด*ในชนิดของมัน ในความหมายที่แม่นยำ: ปัญหาใดก็ตามที่ตรวจคำตอบได้เร็ว (คลาสนี้เรียกว่า NP ย่อจาก "nondeterministic polynomial time") แปลอย่างเป็นระบบ — "ลดรูป" — ไปเป็นอินสแตนซ์ (instance) ของ SAT ที่สมมูลกันได้ และการแปลนั้นใช้การคำนวณเพียงเล็กน้อยและมีประสิทธิภาพ ถ้าแก้ SAT ได้เร็ว ก็แก้*อะไรก็ตาม*ที่ตรวจได้ใน NP ได้เร็ว เพียงแปลมันเป็น SAT ก่อน คุณสมบัตินี้ทำให้ SAT ได้ป้าย NP-complete: complete ในความหมายว่ามันจับความยากทั้งหมดของคลาสทั้งคลาสไว้ได้ (GeeksforGeeks, "Cook–Levin Theorem") ผลลัพธ์เดียวกันในสาระสำคัญถูกค้นพบอีกครั้งในเวลาไล่เลี่ยกัน ราวปี 1973 โดยนักคณิตศาสตร์โซเวียต Leonid Levin ที่ทำงานอย่างเป็นอิสระและแทบจะโดดเดี่ยวสิ้นเชิงอยู่หลังม่านเหล็ก โดยจัดกรอบต่างออกไปเล็กน้อย การค้นพบบรรจบกันสะอาดจนทฤษฎีบทนี้ทุกวันนี้แบกทั้งสองชื่อ คือทฤษฎีบท Cook–Levin เป็นการยอมรับว่าความจริงทางคณิตศาสตร์ที่สำคัญบางครั้งถูกค้นพบสองรอบ โดยคนที่ไม่เคยอ่านงานของกันและกัน
It helps to make the checking-versus-finding distinction concrete with something more familiar than Boolean formulas. Take a hard Sudoku puzzle. If a friend hands you a completed grid and claims it solves the puzzle, verifying the claim is almost mechanical: scan each row, column, and box for repeated digits, and you are done in seconds, however large the grid. But finding that completed grid in the first place, starting from a sparse set of clues, can require searching through a genuinely enormous space of candidate fillings — there is no known shortcut that scales as gracefully as the checking does. Sudoku, scaled up to arbitrary grid sizes, is itself known to be NP-complete. Every problem on this chapter's list shares that same lopsidedness: an answer that is cheap to confirm and, as far as anyone has proven, expensive to construct.
ความต่างระหว่างการตรวจกับการหาจะเป็นรูปธรรมขึ้น ถ้าใช้อะไรที่คุ้นกว่าสูตรตรรกะ เอาซูโดกุข้อยากๆ สักข้อ ถ้าเพื่อนยื่นตารางที่เติมครบแล้วให้และอ้างว่านี่คือคำตอบ การตรวจสอบคำอ้างนั้นแทบเป็นงานกลไก: กวาดดูแต่ละแถว แต่ละหลัก และแต่ละกล่องว่ามีเลขซ้ำไหม จบในไม่กี่วินาที ไม่ว่าตารางจะใหญ่แค่ไหน แต่การ*หา*ตารางที่เติมครบนั้นตั้งแต่ต้น โดยเริ่มจากคำใบ้เพียงไม่กี่ตัว อาจต้องค้นผ่านพื้นที่ของการเติมที่เป็นไปได้ที่ใหญ่จริงๆ — ไม่มีทางลัดที่รู้จักตัวไหนขยายตัวได้ราบรื่นเท่าการตรวจ ซูโดกุที่ขยายไปยังขนาดตารางใดก็ได้นั้น เป็นที่รู้กันว่าเป็น NP-complete ในตัวมันเอง ปัญหาทุกข้อในรายการของบทนี้เบี้ยวข้างแบบเดียวกัน: คำตอบยืนยันได้ถูก และเท่าที่ใครพิสูจน์ได้ สร้างขึ้นมาได้แพง
What a reduction actually does, in the vocabulary this book has been building, deserves to be named as a move in its own right, because it is one of the most powerful weapons a solver can pick up. A reduction says: your problem, however unfamiliar it looks, is secretly a disguised copy of a problem someone has already fully understood. Translate your instance into the known problem's language, solve that, translate the answer back. This is the same act of recognition that let chapter 04's operations researchers see a plywood mill and a wartime diet as the same linear program in different clothes — except here the recognition cuts the opposite way. Instead of finding a shortcut, a reduction can prove that no shortcut is possible, by showing that your problem is at least as hard as one already known to resist every attempt at a shortcut.
สิ่งที่การลดรูป (reduction) ทำ จริงๆ ในคำศัพท์ที่หนังสือเล่มนี้ก่อมา สมควรได้ชื่อเป็นท่าหนึ่งของมันเอง เพราะมันคือหนึ่งในอาวุธที่ทรงพลังที่สุดที่นักแก้ปัญหาหยิบขึ้นมาได้ การลดรูปพูดว่า: ปัญหาของคุณ ไม่ว่าจะดูแปลกหน้าแค่ไหน แท้จริงคือสำเนาปลอมตัวของปัญหาที่มีคนเข้าใจถ่องแท้ไปแล้ว แปลอินสแตนซ์ของคุณเป็นภาษาของปัญหาที่รู้จักนั้น แก้อันนั้น แล้วแปลคำตอบกลับ นี่คือการรู้จำแบบเดียวกับที่ทำให้นักวิจัยดำเนินงาน (operational research, OR) ในบทที่ 04 มองเห็นโรงงานไม้อัดกับสูตรอาหารยามสงครามเป็นกำหนดการเชิงเส้น (linear programming) อันเดียวกันที่ใส่เสื้อผ้าคนละชุด — เว้นแต่ตรงนี้การรู้จำเฉือนไปคนละทาง การลดรูปไม่ได้พบทางลัด แต่พิสูจน์ได้ว่าไม่มีทางลัดใดเป็นไปได้ ด้วยการแสดงว่าปัญหาของคุณยากอย่างน้อยเท่ากับปัญหาที่รู้กันแล้วว่าต้านทานความพยายามหาทางลัดทุกครั้ง
Karp's Rogues' Gallery
หอผู้ร้ายของ Karp
Cook's theorem proved that one problem, SAT, was the hardest of its class. It took Richard Karp's 1972 paper, "Reducibility Among Combinatorial Problems," to show the world how crowded that class actually was. Karp took Cook's result and, using nothing but a chain of reductions, showed that twenty-one further problems — familiar, practical, seemingly unrelated problems that engineers and planners had been quietly struggling with for years — were all secretly NP-complete too (Karp, "Reducibility Among Combinatorial Problems" (1972); Wikipedia, "Karp's 21 NP-complete problems").
ทฤษฎีบทของ Cook พิสูจน์ว่าปัญหาข้อหนึ่ง คือ SAT ยากที่สุดในคลาสของมัน คลาสนั้น*แออัด*แค่ไหนจริงๆ โลกต้องรอบทความปี 1972 ของ Richard Karp ชื่อ "Reducibility Among Combinatorial Problems" Karp หยิบผลของ Cook มา ใช้เพียงโซ่ของการลดรูปเท่านั้น แล้วแสดงว่าปัญหาอีกยี่สิบเอ็ดข้อล้วนเป็น NP-complete เหมือนกันหมดโดยที่ไม่มีใครรู้ — ปัญหาที่คุ้นเคย ใช้งานจริง และดูไม่เกี่ยวกันเลย ที่วิศวกรกับนักวางแผนดิ้นรนกับมันเงียบๆ มาหลายปี (Karp, "Reducibility Among Combinatorial Problems" (1972); Wikipedia, "Karp's 21 NP-complete problems")
Karp's list reads like a tour of applied mathematics: whether a graph can be colored with a given number of colors so that no two connected nodes share one; whether a set of items can be partitioned into two piles of equal total value; whether a network can be covered by a small set of chosen nodes touching every edge; whether a Boolean formula in a certain restricted form is satisfiable at all. These problems had been attacked, separately, by graph theorists, operations researchers, and logicians who had no particular reason to think their struggles were connected. Karp's chain of reductions revealed they were all the same disease wearing twenty-one different costumes — precisely the discovery chapter 04 celebrated in Kantorovich's plywood and Stigler's diet, except that here the shared identity is a shared curse rather than a shared shortcut. If you found an efficient algorithm for any one of them, you would have found one for all of them, and for every problem in NP besides. Nobody has ever found one. Nobody has proven that nobody can. That gap — between decades of failed attempts and a rigorous proof of impossibility — is exactly where the Millennium Prize question lives.
รายการของ Karp อ่านเหมือนทัวร์คณิตศาสตร์ประยุกต์: กราฟหนึ่งระบายสีด้วยจำนวนสีที่กำหนด โดยไม่ให้โหนดสองโหนดที่เชื่อมกันใช้สีเดียวกัน ได้หรือไม่; ชุดของสิ่งของหนึ่งแบ่งเป็นสองกองที่มีมูลค่ารวมเท่ากันได้หรือไม่; เครือข่ายหนึ่งถูกครอบคลุมด้วยชุดโหนดที่เลือกมาไม่กี่โหนดที่แตะทุกเส้นเชื่อมได้หรือไม่; สูตรตรรกะแบบบูลในรูปจำกัดรูปหนึ่งสอดคล้องได้หรือไม่ นักทฤษฎีกราฟ นักวิจัยดำเนินงาน และนักตรรกวิทยาโจมตีปัญหาเหล่านี้แยกกัน และไม่มีเหตุผลอะไรเป็นพิเศษให้คิดว่าความยากลำบากของแต่ละฝ่ายเชื่อมโยงกัน โซ่การลดรูปของ Karp เผยว่าทั้งหมดคือโรคเดียวกันที่สวมเครื่องแต่งกายยี่สิบเอ็ดชุด — การค้นพบแบบเดียวกับที่บทที่ 04 เฉลิมฉลองในไม้อัดของ Kantorovich และสูตรอาหารของ Stigler พอดี เว้นแต่ว่าตรงนี้อัตลักษณ์ร่วมคือ*คำสาป*ร่วม ไม่ใช่ทางลัดร่วม พบอัลกอริทึมที่มีประสิทธิภาพสำหรับข้อใดข้อหนึ่ง ก็เท่ากับพบสำหรับทุกข้อ และสำหรับทุกปัญหาใน NP ด้วย ไม่เคยมีใครพบ ไม่เคยมีใครพิสูจน์ว่าไม่มีใครพบได้ ช่องว่างนั้น — ระหว่างความพยายามที่ล้มเหลวมาหลายทศวรรษ กับบทพิสูจน์ความเป็นไปไม่ได้อย่างเข้มงวด — คือที่ที่คำถามรางวัลมิลเลนเนียมอาศัยอยู่พอดี
The Million-Dollar Question
คำถามหนึ่งล้านดอลลาร์
In 2000, the Clay Mathematics Institute selected seven problems it judged to be the deepest open questions in mathematics and placed a one-million-dollar prize on the first correct solution to each. P versus NP is one of the seven — formally, does every problem whose solutions can be efficiently verified also admit an efficient method of discovery? — and as of this writing it remains unsolved, one of six of the original seven still standing; only the Poincaré conjecture has fallen, to Grigori Perelman in the early 2000s (Clay Mathematics Institute, "P vs NP"; Wikipedia, "Millennium Prize Problems").
ปี 2000 Clay Mathematics Institute เลือกปัญหาเจ็ดข้อที่ตัดสินว่าเป็นคำถามเปิดที่ลึกที่สุดในคณิตศาสตร์ และตั้งรางวัลหนึ่งล้านดอลลาร์ให้คำตอบที่ถูกต้องคำตอบแรกของแต่ละข้อ P versus NP เป็นหนึ่งในเจ็ดข้อนั้น — พูดอย่างเป็นทางการคือ ปัญหาทุกข้อที่*ตรวจสอบ*คำตอบได้อย่างมีประสิทธิภาพ ยอมให้มีวิธี*ค้นพบ*ที่มีประสิทธิภาพด้วยหรือไม่ — และ ณ เวลาที่เขียนอยู่นี้ยังไม่มีใครแก้ได้ มันเป็นหนึ่งในหกข้อจากเจ็ดข้อเดิมที่ยังยืนอยู่; มีเพียงข้อความคาดการณ์ Poincaré เท่านั้นที่ล้มลง โดยฝีมือของ Grigori Perelman ช่วงต้นทศวรรษ 2000 (Clay Mathematics Institute, "P vs NP"; Wikipedia, "Millennium Prize Problems")
The traveling salesman problem has become this chapter's emblem, and for good reason: it is easy enough to state to a child (find the shortest possible route visiting every city on a list exactly once and returning home) and hard enough that no one has ever found a way to solve it exactly, for large instances, that beats trying an amount of work growing explosively with the number of cities. It sits, alongside SAT and Karp's twenty-one, on the far side of the wall — not proven impossible to solve quickly, but proven exactly as hard as every other problem in the same enormous, unresolved family.
ปัญหาพนักงานขายเดินทาง (traveling salesman problem) กลายเป็นสัญลักษณ์ของบทนี้ ด้วยเหตุผลที่ดี: มันง่ายพอจะเล่าให้เด็กฟัง (หาเส้นทางที่สั้นที่สุดเท่าที่จะเป็นไปได้ ที่แวะทุกเมืองในรายการเมืองละครั้งพอดีแล้วกลับบ้าน) และยากพอจนไม่เคยมีใครหาวิธีแก้มันแบบตรงเป๊ะสำหรับอินสแตนซ์ขนาดใหญ่ ที่ชนะการลองด้วยปริมาณงานที่โตระเบิดตามจำนวนเมืองได้ มันนั่งอยู่ข้างๆ SAT และยี่สิบเอ็ดข้อของ Karp บนอีกฟากของกำแพง — ไม่มีใครพิสูจน์ว่ามันแก้เร็วไม่ได้ แต่มีบทพิสูจน์ว่ามันยากเท่ากับปัญหาอื่นทุกข้อในตระกูลมหึมาที่ยังไม่มีข้อยุติตระกูลเดียวกัน เป๊ะๆ
It is worth pausing to be honest about what "the wall" actually claims, because it is easy to overstate. Nobody has proven P ≠ NP. It remains logically possible — though almost no computer scientist believes it — that some ingenious algorithm for SAT is waiting to be found, and that finding it would efficiently solve every problem on Karp's list and every problem like them at a stroke. What has been proven, with total rigor, is the equivalence: solve one member of this vast family efficiently and you have solved them all. The wall may or may not be permanent. What is certain is that it is the same wall, everywhere you press against it.
"กำแพง" อ้างอะไรกันแน่ ควรหยุดพูดตามตรงสักครู่ เพราะมันเผลออ้างเกินจริงได้ง่าย ไม่มีใครพิสูจน์ว่า P ≠ NP ยังเป็นไปได้ในเชิงตรรกะ — แม้แทบไม่มีนักวิทยาการคอมพิวเตอร์คนไหนเชื่อ — ว่าอัลกอริทึมอันชาญฉลาดสักตัวสำหรับ SAT กำลังรอให้ค้นพบอยู่ และการพบมันจะแก้ทุกปัญหาในรายการของ Karp และทุกปัญหาแบบเดียวกันได้อย่างมีประสิทธิภาพในคราวเดียว สิ่งที่พิสูจน์แล้วอย่างเข้มงวดเต็มที่คือ*ความสมมูล*: แก้สมาชิกหนึ่งตัวของตระกูลมหึมานี้ได้อย่างมีประสิทธิภาพ ก็เท่ากับแก้ได้ทั้งตระกูล กำแพงนี้จะถาวรหรือไม่ ยังไม่มีใครรู้ สิ่งที่แน่คือมันเป็นกำแพงเดียวกัน ไม่ว่าจะไปดันตรงไหน
Life at the Wall
ชีวิตที่เชิงกำแพง
If the theory stopped here, this would be a chapter about despair: a proof that a huge swath of practically important problems cannot be solved exactly and efficiently, full stop. What actually happened next is more interesting, and it is the part of this chapter's story that keeps this book's central thesis alive even at its darkest point — because solvers, faced with a wall, did not stop. They found doors.
ถ้าทฤษฎีหยุดอยู่แค่นี้ บทนี้ก็เป็นบทว่าด้วยความสิ้นหวัง: บทพิสูจน์ว่าปัญหาสำคัญในทางปฏิบัติจำนวนมากแก้แบบตรงเป๊ะและมีประสิทธิภาพไม่ได้ จบ สิ่งที่เกิดขึ้นจริงต่อจากนั้นน่าสนใจกว่า และมันคือส่วนของเรื่องเล่าในบทนี้ที่ทำให้ข้อเสนอใจกลางของหนังสือเล่มนี้ยังมีชีวิตอยู่แม้ในจุดที่มืดที่สุด — เพราะนักแก้ปัญหาที่เจอกำแพงไม่ได้หยุด พวกเขาหาประตูเจอ
The first door is approximation: give up on finding the provably optimal answer and settle, deliberately, for a solution guaranteed to be within some fixed, known factor of optimal. In 1976, Nicos Christofides published an algorithm for a common variant of the traveling salesman problem — one where the triangle inequality holds, meaning a direct route between two cities is never longer than a detour through a third — that is guaranteed to find a tour no more than 50 percent longer than the true shortest possible tour, no matter the instance. Remarkably, more than four decades later, Christofides' 1.5-factor guarantee for this problem had still not been beaten by any published algorithm as of the early 2020s, a striking testament to how hard even bounded progress on an NP-complete problem can be (arXiv, "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem"). An approximation algorithm does not defeat the wall. It negotiates terms with it: not the best answer, but a provably good-enough one, delivered in a time that does not explode.
ประตูบานแรกคือการประมาณ (approximation): เลิกหาคำตอบที่พิสูจน์ได้ว่าเหมาะที่สุด แล้วตั้งใจยอมรับคำตอบที่รับประกันว่าห่างจากค่าเหมาะที่สุดไม่เกินตัวคูณค่าหนึ่งที่ตายตัวและรู้ค่า ปี 1976 Nicos Christofides ตีพิมพ์อัลกอริทึมสำหรับปัญหาพนักงานขายเดินทางรูปแบบที่พบบ่อยแบบหนึ่ง — แบบที่อสมการสามเหลี่ยมเป็นจริง คือเส้นทางตรงระหว่างสองเมืองไม่มีวันยาวกว่าการอ้อมผ่านเมืองที่สาม — อัลกอริทึมนี้รับประกันว่าจะหาทัวร์ที่ยาวกว่าทัวร์ที่สั้นที่สุดจริงไม่เกิน 50 เปอร์เซ็นต์ ไม่ว่าอินสแตนซ์จะเป็นอย่างไร กว่าสี่ทศวรรษให้หลัง การรับประกันตัวคูณ 1.5 ของ Christofides สำหรับปัญหานี้ยังไม่ถูกอัลกอริทึมที่ตีพิมพ์ตัวไหนโค่นได้เลย ณ ช่วงต้นทศวรรษ 2020 ตัวเลขนั้นบอกเองว่าความคืบหน้าแม้แต่แบบ*มีขอบเขต*บนปัญหา NP-complete ยากเพียงใด (arXiv, "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem") อัลกอริทึมประมาณไม่ได้เอาชนะกำแพง มันเจรจาเงื่อนไขกับกำแพง: ไม่ใช่คำตอบที่ดีที่สุด แต่เป็นคำตอบที่*พิสูจน์ได้*ว่าดีพอ ส่งมอบในเวลาที่ไม่ระเบิด
The second door is randomization — the same willingness to trade certainty for speed that chapter 04 met in Monte Carlo methods, applied here to combinatorial search rather than physical simulation. A randomized algorithm makes some of its choices by coin flip rather than exhaustive comparison, and for many hard problems this yields algorithms that are fast on average and wrong only with controllable, vanishingly small probability — a guaranteed-correct answer traded for an almost-certainly-correct one delivered far sooner. The clearest everyday example sits, fittingly, inside the very cryptography this chapter is about to turn to: before RSA can lock anything, it first needs two very large prime numbers, and testing an enormous candidate number for primality by trial division is itself hopelessly slow. The Miller–Rabin test, devised by Gary Miller in 1976 and made fully practical by Michael Rabin shortly after, picks random witnesses and checks each one against the candidate number; a composite number will be caught with at least even odds by any single random witness, so after fifty independent draws the chance of a wrong answer falls below one in a quadrillion — small enough that every RSA key generated today is built on primes accepted by a test that is not, strictly, certain, only certain enough (Cornell CS4820, "The Miller-Rabin Randomized Primality Test").
ประตูบานที่สองคือการสุ่ม (randomization) — ความเต็มใจแลกความแน่นอนกับความเร็วแบบเดียวกับที่บทที่ 04 พบในวิธีมอนติคาร์โล คราวนี้ใช้กับการค้นหาเชิงการจัดหมู่แทนการจำลองทางกายภาพ อัลกอริทึมแบบสุ่มตัดสินใจบางส่วนด้วยการโยนเหรียญแทนการเทียบทุกทางเลือก สำหรับปัญหายากหลายข้อ วิธีนี้ให้อัลกอริทึมที่เร็วโดยเฉลี่ยและผิดด้วยความน่าจะเป็นที่ควบคุมได้และเล็กจนแทบหายไป — แลกคำตอบที่รับประกันว่าถูก กับคำตอบที่แทบจะแน่นอนว่าถูกและมาถึงเร็วกว่ามาก ตัวอย่างในชีวิตประจำวันที่ชัดที่สุดอยู่ในวิทยาการรหัสลับที่บทนี้กำลังจะหันไปพูดถึงพอดี และก็เหมาะเจาะดี: ก่อน RSA จะล็อกอะไรได้ มันต้องมีจำนวนเฉพาะขนาดใหญ่มากสองจำนวนก่อน และการทดสอบว่าจำนวนมหึมาที่เป็นตัวเลือกเป็นจำนวนเฉพาะหรือไม่ด้วยการหารไล่ ตัวมันเองก็ช้าจนหมดหวัง การทดสอบ Miller–Rabin ที่ Gary Miller คิดขึ้นในปี 1976 และ Michael Rabin ทำให้ใช้งานได้จริงเต็มที่ในเวลาไม่นานหลังจากนั้น เลือกพยานแบบสุ่มขึ้นมาแล้วตรวจแต่ละตัวกับจำนวนที่เป็นตัวเลือก; พยานสุ่มตัวเดียวจับจำนวนประกอบได้ด้วยโอกาสอย่างน้อยครึ่งต่อครึ่ง ดังนั้นหลังจับพยานอิสระห้าสิบตัว โอกาสได้คำตอบผิดตกลงต่ำกว่าหนึ่งในพันล้านล้าน — เล็กพอจนกุญแจ RSA ทุกดอกที่สร้างขึ้นทุกวันนี้ตั้งอยู่บนจำนวนเฉพาะที่ผ่านการทดสอบที่พูดอย่างเคร่งครัดแล้วไม่ได้แน่นอน แค่แน่นอนพอ (Cornell CS4820, "The Miller-Rabin Randomized Primality Test")
The third door is the most surprising, and it is the one modern computing quietly walks through every day without most of its users ever noticing. In the decades since Cook and Levin's theorem, engineers built increasingly sophisticated SAT solvers — programs that attempt to find a satisfying assignment for exactly the problem Cook proved NP-complete in the first place. The modern generation of these tools, built around a technique called conflict-driven clause learning (CDCL), does something that should, on paper, be impossible: it routinely solves real-world SAT instances with millions of variables and clauses, arising from chip verification, software testing, and scheduling, in practical amounts of time (arXiv, "Relating Complexity-theoretic Parameters with SAT Solver Performance"). CDCL works by learning from its own failures mid-search: every time it reaches a dead end, it derives a new logical constraint — a "clause" — summarizing why that dead end occurred, adds it permanently to the problem, and uses it to prune away every future branch that would repeat the same mistake for the same underlying reason. Over the course of a long search, the solver effectively rewrites the problem it is solving, filling it with accumulated scar tissue from every wrong turn, and the accumulated scars turn out to make the remaining search dramatically smaller. This does not contradict the Cook–Levin theorem. Worst-case instances of SAT, carefully constructed to defeat exactly this kind of learning, remain exponentially hard, and always will unless P equals NP. But the industrial instances that show up in real chip designs and real schedules are, empirically, richly structured rather than adversarially worst-case, and researchers have spent years trying to characterize exactly what kind of hidden structure — community clustering, "backdoor" variable sets, low treewidth — CDCL solvers are quietly exploiting to walk straight through problems that complexity theory says should be untouchable. The wall is real, in the worst case, for every instance anyone could construct. It is also, for the instances that actually show up in practice, full of doors nobody predicted would be there.
ประตูบานที่สามน่าประหลาดใจที่สุด และเป็นบานที่คอมพิวเตอร์สมัยใหม่เดินผ่านเงียบๆ ทุกวันโดยที่ผู้ใช้ส่วนใหญ่ไม่เคยสังเกต ในหลายทศวรรษหลังทฤษฎีบทของ Cook กับ Levin วิศวกรสร้าง SAT solver ที่ซับซ้อนขึ้นเรื่อยๆ — โปรแกรมที่พยายามหาการกำหนดค่าที่ทำให้สูตรเป็นจริง สำหรับปัญหาที่ Cook พิสูจน์ว่าเป็น NP-complete ตั้งแต่แรกนั่นเอง เครื่องมือรุ่นใหม่ที่สร้างรอบเทคนิคชื่อ conflict-driven clause learning (CDCL) ทำสิ่งที่บนกระดาษควรเป็นไปไม่ได้: มันแก้อินสแตนซ์ SAT ในโลกจริงที่มีตัวแปรและอนุประโยคเป็น*ล้าน* จากการตรวจสอบชิป การทดสอบซอฟต์แวร์ และการจัดตาราง ได้เป็นปกติ ในเวลาที่ใช้งานได้จริง (arXiv, "Relating Complexity-theoretic Parameters with SAT Solver Performance") CDCL เรียนรู้จากความล้มเหลวของตัวเองระหว่างค้นหา: ทุกครั้งที่ไปถึงทางตัน มันอนุมานข้อจำกัดทางตรรกะข้อใหม่ — "อนุประโยค (clause)" — ที่สรุปว่า*ทำไม*ทางตันนั้นถึงเกิด เพิ่มมันเข้าไปในปัญหาอย่างถาวร แล้วใช้มันตัดกิ่งทุกกิ่งในอนาคตที่จะผิดซ้ำแบบเดิมด้วยเหตุผลพื้นฐานเดียวกันทิ้ง ตลอดการค้นหาที่ยาวนาน ตัวแก้ปัญหาเท่ากับเขียนปัญหาที่มันกำลังแก้ขึ้นใหม่ เติมมันด้วยเนื้อแผลเป็นที่สะสมจากทุกการเลี้ยวผิด และแผลเป็นที่สะสมนั้นกลับทำให้การค้นหาที่เหลือเล็กลงมาก เรื่องนี้ไม่ได้ขัดกับทฤษฎีบท Cook–Levin อินสแตนซ์กรณีเลวร้ายที่สุดของ SAT ที่ถูกสร้างขึ้นอย่างพิถีพิถันเพื่อเอาชนะการเรียนรู้แบบนี้พอดี ยังคงยากแบบเอกซ์โพเนนเชียล และจะยากอย่างนั้นตลอดไป เว้นแต่ P จะเท่ากับ NP แต่อินสแตนซ์*ระดับอุตสาหกรรม*ที่โผล่มาในการออกแบบชิปจริงและตารางงานจริง จากการวัดจริงมีโครงสร้างหนาแน่น ไม่ใช่กรณีเลวร้ายที่สุดที่ถูกออกแบบมาเล่นงาน นักวิจัยใช้เวลาหลายปีพยายามระบุให้ได้ว่าโครงสร้างที่ซ่อนอยู่ชนิดไหนกันแน่ — การจับกลุ่มเป็นชุมชน ชุดตัวแปร "ประตูหลัง" ค่า treewidth ต่ำ — ที่ SAT solver แบบ CDCL แอบใช้ประโยชน์อยู่เงียบๆ เพื่อเดินทะลุปัญหาที่ทฤษฎีความซับซ้อน (complexity) บอกว่าควรจะแตะไม่ได้ กำแพงนั้นเป็นของจริง ในกรณีเลวร้ายที่สุด สำหรับทุกอินสแตนซ์ที่ใครก็ตามจะสร้างขึ้นได้ และสำหรับอินสแตนซ์ที่โผล่มาในทางปฏิบัติจริงๆ มันก็เต็มไปด้วยประตูที่ไม่มีใครทำนายว่าจะอยู่ตรงนั้น
The Wall as Fortress
กำแพงในฐานะป้อมปราการ
The final turn in this chapter's story inverts everything that came before it, and it is the most consequential inversion in this book. Every solver so far has treated hardness as an obstacle: a wall to be reduced away from, approximated around, or randomized through. In 1977, three MIT researchers — Ron Rivest, Adi Shamir, and Leonard Adleman — realized that hardness could instead be the product.
จุดหักครั้งสุดท้ายในเรื่องเล่าของบทนี้กลับทุกอย่างที่มาก่อนหน้า และเป็นการกลับด้านที่ส่งผลมากที่สุดในหนังสือเล่มนี้ นักแก้ปัญหาทุกคนจนถึงตอนนี้ปฏิบัติกับความยาก (hardness) เหมือนอุปสรรค: กำแพงที่ต้องลดรูปหนีออกมา ประมาณอ้อมไป หรือสุ่มทะลุผ่าน ปี 1977 นักวิจัย MIT สามคน — Ron Rivest, Adi Shamir และ Leonard Adleman — ตระหนักว่าความยากเป็น*ตัวสินค้า*ได้แทน
Their cryptosystem, which took the researchers' initials as its name, RSA, is built on a specific, carefully chosen instance of computational hardness: multiplying two very large prime numbers together is fast, taking a computer a fraction of a second even for numbers hundreds of digits long, but factoring the resulting product back into its two original primes, without already knowing them, has no known efficient method — you are back to something resembling brute-force search through an astronomically large space of candidate factors (Splunk, "RSA Algorithm in Cryptography: Rivest Shamir Adleman Explained"). Anyone can publish the product — the "public key" — and use it to lock a message. Only someone who knows the two original primes — the "private key" — can unlock it efficiently; everyone else faces a computational wall as real as any traveling salesman's. RSA is, technically, believed to rely on the hardness of integer factorization rather than being proven NP-complete in the strict Cook–Levin sense — factorization sits in a curious, not-fully-resolved corner of complexity theory, apparently hard but not known to be NP-complete itself. What matters for this chapter's purposes is the philosophical hinge, not the technical fine print: an entire branch of applied mathematics discovered that a wall no one can climb is exactly as valuable as a treasure no one can steal. Every secure connection to a bank, a hospital record, or an encrypted message rests, at bottom, on the same kind of hardness that makes the traveling salesman problem resist every solver's cleverness. One field's dead end is another field's foundation.
ระบบรหัสลับของพวกเขา คือ RSA ใช้อักษรย่อของนักวิจัยทั้งสามเป็นชื่อ และสร้างขึ้นบนอินสแตนซ์ของความยากเชิงการคำนวณที่เจาะจงและเลือกมาอย่างพิถีพิถัน: คูณจำนวนเฉพาะขนาดใหญ่มากสองจำนวนเข้าด้วยกันนั้นเร็ว คอมพิวเตอร์ใช้เวลาเสี้ยววินาทีแม้กับจำนวนที่ยาวหลายร้อยหลัก แต่การ*แยกตัวประกอบ*ผลคูณที่ได้กลับไปเป็นจำนวนเฉพาะสองจำนวนตั้งต้น โดยไม่รู้มันอยู่ก่อน ไม่มีวิธีที่มีประสิทธิภาพที่รู้จักเลย — กลับไปสู่อะไรที่คล้ายการค้นหาแบบไล่ทุกทาง (brute force) ผ่านพื้นที่ของตัวประกอบที่เป็นไปได้ที่ใหญ่ระดับดาราศาสตร์ (Splunk, "RSA Algorithm in Cryptography: Rivest Shamir Adleman Explained") ใครก็ประกาศผลคูณนั้นได้ — "กุญแจสาธารณะ" — และใช้มันล็อกข้อความ มีเพียงคนที่รู้จำนวนเฉพาะตั้งต้นสองจำนวน — "กุญแจส่วนตัว" — เท่านั้นที่ปลดล็อกได้อย่างมีประสิทธิภาพ; คนอื่นทั้งหมดเจอกำแพงเชิงการคำนวณที่เป็นของจริงพอๆ กับกำแพงของพนักงานขายเดินทาง ในทางเทคนิค เชื่อกันว่า RSA พึ่งความยากของการแยกตัวประกอบจำนวนเต็ม มากกว่าจะมีบทพิสูจน์ว่าเป็น NP-complete ในความหมายเคร่งครัดแบบ Cook–Levin — การแยกตัวประกอบนั่งอยู่ในมุมที่แปลกและยังไม่มีข้อยุติเต็มที่ของทฤษฎีความซับซ้อน ดูจะยาก แต่ไม่มีใครรู้ว่าตัวมันเองเป็น NP-complete หรือไม่ สิ่งที่สำคัญสำหรับเป้าหมายของบทนี้คือบานพับทางปรัชญา ไม่ใช่ตัวหนังสือตัวเล็กเชิงเทคนิค: คณิตศาสตร์ประยุกต์ทั้งสาขาค้นพบว่ากำแพงที่ไม่มีใครปีนได้ มีค่าเท่ากับสมบัติที่ไม่มีใครขโมยได้พอดี ทุกการเชื่อมต่อที่ปลอดภัยไปยังธนาคาร เวชระเบียนของโรงพยาบาล หรือข้อความที่เข้ารหัส ล้วนตั้งอยู่บนความยากชนิดเดียวกันกับที่ทำให้ปัญหาพนักงานขายเดินทางต้านทานความฉลาดของนักแก้ปัญหาทุกคน ทางตันของสาขาหนึ่งคือรากฐานของอีกสาขาหนึ่ง
Hardness Is Information
ความยากคือข้อมูล
Step back, and this chapter completes something chapter 00 promised and chapter 04 and 05 built toward: the honest limits of this book's central claim. "Great solvers do not search harder; they change the space until the path is short" has held, gloriously, across every chapter so far — Euler's dots, Blackett's convoys, Dijkstra's frontier, A*'s admissible optimism. NP-completeness is this book's proof that the claim has a genuine boundary. Some spaces, as far as anyone has ever proven or is likely to prove soon, cannot be compressed by any representation change, however clever — not because no one has been clever enough yet, but because Cook, Levin, and Karp showed that compressing any one of them efficiently would compress all of them efficiently, and seventy years of the finest minds in computer science trying to do exactly that have come back empty-handed.
บทนี้ปิดสิ่งที่บทที่ 00 สัญญาไว้ และบทที่ 04 กับ 05 ปูทางมาถึง: ขีดจำกัดที่ซื่อสัตย์ของข้ออ้างใจกลางของหนังสือเล่มนี้ ถอยออกมามองจะเห็นชัด "นักแก้ปัญหาที่ยิ่งใหญ่ไม่ค้นหาหนักขึ้น — เขาเปลี่ยนพื้นที่จนเส้นทางสั้นลง" ยืนอยู่ได้ตลอดทุกบทที่ผ่านมา — จุดของ Euler กองเรือคุ้มกันของ Blackett แนวหน้าของ Dijkstra การมองโลกในแง่ดีแบบ admissible ของ A\* NP-completeness คือบทพิสูจน์ของเล่มนี้ว่าข้ออ้างนั้นมีขอบเขตจริง พื้นที่บางแบบบีบอัดไม่ได้ด้วยการเปลี่ยนรูปแบบการแทนปัญหา (representation) ใดๆ ไม่ว่าจะฉลาดแค่ไหน เท่าที่ใครเคยพิสูจน์ได้หรือน่าจะพิสูจน์ได้ในเร็ววัน เหตุผลไม่ใช่ว่ายังไม่มีใครฉลาดพอ Cook, Levin และ Karp แสดงให้เห็นว่าถ้าบีบอัดพื้นที่*ข้อใดข้อหนึ่ง*ได้อย่างมีประสิทธิภาพ ก็จะบีบอัด*ทุกข้อ*ได้อย่างมีประสิทธิภาพไปด้วย และเจ็ดสิบปีที่สมองดีที่สุดในวิทยาการคอมพิวเตอร์พยายามทำเรื่องนั้นพอดี ก็กลับมามือเปล่า
But notice what kind of knowledge that failure actually is. Knowing that a problem sits behind the NP-complete wall is not the absence of a solution — it is a piece of information about the problem, as concrete and useful as knowing its size or its symmetries. It tells you, immediately, not to waste a career hunting for an exact, always-fast algorithm. It tells you to reach instead for approximation, randomization, or a solver built to exploit whatever real-world structure your instances actually have, rather than their theoretical worst case. And, in RSA's case, it tells you the wall itself might be worth more standing than knocked down. Naming the wall is itself an act of solving — it is the last, hardest-won representation change this section of the book has to offer: reframing "I cannot find a fast algorithm" from a personal failure into a proven structural fact about the space, and then choosing, with open eyes, which door to walk through instead.
แต่ให้สังเกตว่าความล้มเหลวนั้นเป็นความรู้ชนิดไหนกันแน่ การรู้ว่าปัญหาข้อหนึ่งอยู่หลังกำแพง NP-complete ไม่ใช่การไม่มีคำตอบ — มันคือ*ชิ้นข้อมูลเกี่ยวกับปัญหานั้น* เป็นรูปธรรมและใช้ได้จริงพอๆ กับการรู้ขนาดหรือความสมมาตรของมัน มันบอกทันทีว่าอย่าผลาญทั้งอาชีพไปกับการล่าอัลกอริทึมที่ตรงเป๊ะและเร็วเสมอ มันบอกให้เอื้อมไปหาการประมาณ การสุ่ม หรือตัวแก้ที่สร้างมาเพื่อใช้ประโยชน์จากโครงสร้างในโลกจริงเท่าที่อินสแตนซ์ของคุณมีอยู่จริง แทนกรณีเลวร้ายที่สุดในทางทฤษฎีของมัน และในกรณีของ RSA มันบอกว่ากำแพงที่ยังยืนอยู่อาจมีค่ามากกว่ากำแพงที่ถูกทุบลง การเรียกชื่อกำแพงเป็นการแก้ปัญหาในตัวมันเอง — มันคือการเปลี่ยน representation ครั้งสุดท้ายและได้มายากที่สุดที่ส่วนนี้ของหนังสือมีให้: เปลี่ยนกรอบ "ฉันหาอัลกอริทึมที่เร็วไม่ได้" จากความล้มเหลวส่วนตัว ให้เป็นข้อเท็จจริงเชิงโครงสร้างที่พิสูจน์แล้วเกี่ยวกับพื้นที่ แล้วเลือกด้วยตาที่เปิดกว้างว่าจะเดินผ่านประตูบานไหนแทน
The Move
ท่าประจำบท
Move 06 — Name the wall, then trade: reduce, approximate, randomize, or repurpose the hardness.
Move 06 — เรียกชื่อกำแพง แล้วแลก: ลดรูป ประมาณ สุ่ม หรือเอาความยากไปใช้ประโยชน์
- Before searching for years, check whether your problem is a known monster in disguise. A reduction from a Karp-list problem, or from SAT itself, is proof that no one else has found a fast general solution either — that is worth knowing before, not after, a career's worth of failed attempts.
- When exact and fast cannot both be had, choose which one to give up, deliberately. Christofides' bound trades exactness for a guaranteed-good approximation; Monte Carlo-style randomization trades certainty for overwhelming probability. Both are engineering decisions, not defeats.
- Check whether your actual instances are the adversarial worst case or the friendly common case. CDCL solvers prove that "NP-complete in theory" and "intractable in your specific data" are different claims; industrial SAT is proof that real problems are often far kinder than the theorems that bound them.
- Ask whether the hardness itself has value. RSA shows that a wall no one can climb can be turned into a fortress. Before treating intractability as pure obstacle, ask who would pay for a problem that stays hard forever.
- ก่อนจะค้นหาอยู่หลายปี ตรวจก่อนว่าปัญหาของคุณคือสัตว์ประหลาดที่รู้จักกันดีซึ่งปลอมตัวมาหรือเปล่า การลดรูปจากปัญหาในรายการของ Karp หรือจาก SAT เอง คือหลักฐานว่าไม่มีใครอื่นหาคำตอบทั่วไปที่เร็วเจอเหมือนกัน — เรื่องนี้ควรรู้ก่อน ไม่ใช่หลัง ความพยายามที่ล้มเหลวคุ้มค่าทั้งอาชีพ
- เมื่อตรงเป๊ะกับเร็วมีพร้อมกันไม่ได้ จงเลือกอย่างตั้งใจว่าจะสละอันไหน ขอบเขตของ Christofides แลกความตรงเป๊ะกับการประมาณที่รับประกันว่าดี; การสุ่มแบบมอนติคาร์โลแลกความแน่นอนกับความน่าจะเป็นที่ท่วมท้น ทั้งคู่คือการตัดสินใจเชิงวิศวกรรม ไม่ใช่ความพ่ายแพ้
- ตรวจว่าอินสแตนซ์จริงของคุณคือกรณีเลวร้ายที่สุดที่ถูกออกแบบมาเล่นงาน หรือกรณีทั่วไปที่เป็นมิตร SAT solver แบบ CDCL พิสูจน์ว่า "NP-complete ในทางทฤษฎี" กับ "จัดการไม่ไหว (intractable) ในข้อมูลเฉพาะของคุณ" เป็นคนละข้ออ้างกัน; SAT ระดับอุตสาหกรรมคือหลักฐานว่าปัญหาจริงมักใจดีกว่าทฤษฎีบทที่ตีกรอบมันไว้มาก
- ถามว่าความยากนั้นเองมีค่าหรือไม่ RSA แสดงให้เห็นว่ากำแพงที่ไม่มีใครปีนได้ เปลี่ยนเป็นป้อมปราการได้ ก่อนจะปฏิบัติกับความจัดการไม่ไหวเหมือนอุปสรรคล้วนๆ ให้ถามว่าใครจะยอมจ่ายเงินซื้อปัญหาที่ยากอยู่อย่างนั้นตลอดไป
Next — Chapter 07 · Gallery I: The Single Move: theory now gives way to a gallery. Five solvers, four centuries, one move each — the history this book has built in the abstract, made concrete, one great solve at a time.
ต่อไป — บทที่ 07 · หอเรื่องเล่า I: ท่าเดียวจบ: ทฤษฎีถึงคราวหลีกทางให้หอเรื่องเล่า นักแก้ปัญหาห้าคน สี่ศตวรรษ คนละหนึ่งท่า — ประวัติศาสตร์ที่หนังสือเล่มนี้ก่อไว้ในเชิงนามธรรม ถูกทำให้เป็นรูปธรรม ทีละการแก้ครั้งใหญ่