06 · กำแพง
เส้นทางที่สั้นที่สุด — ประวัติศาสตร์ของศิลปะและศาสตร์แห่งการแก้ปัญหา
จดหมายถึงชายที่กำลังจะตาย
ฤดูใบไม้ผลิปี 1956 John von Neumann อายุห้าสิบสาม กำลังจะตายด้วยโรคมะเร็ง และถูกกักตัวอยู่ในโรงพยาบาล Walter Reed นานขึ้นทุกที ผลงานที่เคยไหลออกมาไม่หยุดหดเหลือเท่าที่ร่างกายที่กำลังทรุดจะยอมให้ทำ เดือนมีนาคมปีนั้น Kurt Gödel เขียนจดหมายถึงเขา Gödel คือเพื่อนเก่าจากเวียนนา นักตรรกวิทยาที่ทุบความฝันของ Hilbert เรื่องคณิตศาสตร์ที่ครบถ้วนและสอดคล้องในตัวเองจนแตกเมื่อยี่สิบห้าปีก่อน ตามคำบอกเล่าส่วนใหญ่ จดหมายฉบับนั้นส่วนหนึ่งเขียนขึ้นเพื่อหาอะไรให้สมองที่เฉียบแหลมและกำลังจะดับได้ขบคิด นอกเหนือไปจากความเสื่อมถอยของตัวมันเอง
คำถามของ 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 เสียชีวิตในเดือนกุมภาพันธ์ปีถัดมา เขาเคยตอบหรือไม่ ไม่มีใครรู้; ไม่มีคำตอบหลงเหลือมาถึงเรา คำถามนี้นอนนิ่งอยู่อีกสิบห้าปี แทบไม่มีใครนอกวงเล็กๆ สังเกตเห็น
บทนี้ว่าด้วยสิ่งที่เกิดขึ้นเมื่อคำถามนี้ได้คำตอบในที่สุด — ไม่ใช่ถูกแก้ แต่ได้รูปทรงที่ชัดเจนและได้ชื่อ — และว่าด้วยการค้นพบที่แปลกและมีคมสองด้านที่ตามมา ปัญหาบางข้อดูจะต้านทานการเปลี่ยนกรอบ (reframe) อันชาญฉลาด*ทุกแบบ*ที่หนังสือเล่มนี้ยกย่องมาจนถึงตอนนี้ และเมื่อพิสูจน์การต้านทานนั้นได้แล้ว มันก็กลายเป็นความรู้ชนิดหนึ่งในตัวมันเอง
โรคเดียว อาการมากมาย
สาขานี้ถือกำเนิดอย่างเป็นทางการในปี 1971 เมื่อ Stephen Cook ซึ่งตอนนั้นอยู่ที่ University of Toronto ตีพิมพ์บทความสั้นชื่อ "The Complexity of Theorem-Proving Procedures" Cook ศึกษาปัญหาความสอดคล้องได้แบบบูล (Boolean satisfiability) หรือ SAT: ให้สูตรตรรกะที่สร้างจากตัวแปรที่แต่ละตัวเป็น TRUE หรือ FALSE ได้ เชื่อมกันด้วย AND, OR และ NOT — มีการกำหนดค่า*ชุดใดชุดหนึ่ง*ที่ทำให้สูตรทั้งสูตรเป็นจริงหรือไม่ ตรวจการกำหนดค่าที่เสนอมานั้นง่ายมาก — แทนค่าลงไปแล้วประเมิน หาการกำหนดค่าสักชุดนั้นอีกเรื่อง เมื่อสูตรมีตัวแปรเป็นพันตัวที่ล็อกเข้าด้วยกันด้วยข้อจำกัดเป็นพันข้อ ดูจะต้องใช้อะไรที่ใกล้เคียงกับการลองทุกความเป็นไปได้
การหยั่งเห็น (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 เป็นการยอมรับว่าความจริงทางคณิตศาสตร์ที่สำคัญบางครั้งถูกค้นพบสองรอบ โดยคนที่ไม่เคยอ่านงานของกันและกัน
ความต่างระหว่างการตรวจกับการหาจะเป็นรูปธรรมขึ้น ถ้าใช้อะไรที่คุ้นกว่าสูตรตรรกะ เอาซูโดกุข้อยากๆ สักข้อ ถ้าเพื่อนยื่นตารางที่เติมครบแล้วให้และอ้างว่านี่คือคำตอบ การตรวจสอบคำอ้างนั้นแทบเป็นงานกลไก: กวาดดูแต่ละแถว แต่ละหลัก และแต่ละกล่องว่ามีเลขซ้ำไหม จบในไม่กี่วินาที ไม่ว่าตารางจะใหญ่แค่ไหน แต่การ*หา*ตารางที่เติมครบนั้นตั้งแต่ต้น โดยเริ่มจากคำใบ้เพียงไม่กี่ตัว อาจต้องค้นผ่านพื้นที่ของการเติมที่เป็นไปได้ที่ใหญ่จริงๆ — ไม่มีทางลัดที่รู้จักตัวไหนขยายตัวได้ราบรื่นเท่าการตรวจ ซูโดกุที่ขยายไปยังขนาดตารางใดก็ได้นั้น เป็นที่รู้กันว่าเป็น NP-complete ในตัวมันเอง ปัญหาทุกข้อในรายการของบทนี้เบี้ยวข้างแบบเดียวกัน: คำตอบยืนยันได้ถูก และเท่าที่ใครพิสูจน์ได้ สร้างขึ้นมาได้แพง
สิ่งที่การลดรูป (reduction) ทำ จริงๆ ในคำศัพท์ที่หนังสือเล่มนี้ก่อมา สมควรได้ชื่อเป็นท่าหนึ่งของมันเอง เพราะมันคือหนึ่งในอาวุธที่ทรงพลังที่สุดที่นักแก้ปัญหาหยิบขึ้นมาได้ การลดรูปพูดว่า: ปัญหาของคุณ ไม่ว่าจะดูแปลกหน้าแค่ไหน แท้จริงคือสำเนาปลอมตัวของปัญหาที่มีคนเข้าใจถ่องแท้ไปแล้ว แปลอินสแตนซ์ของคุณเป็นภาษาของปัญหาที่รู้จักนั้น แก้อันนั้น แล้วแปลคำตอบกลับ นี่คือการรู้จำแบบเดียวกับที่ทำให้นักวิจัยดำเนินงาน (operational research, OR) ในบทที่ 04 มองเห็นโรงงานไม้อัดกับสูตรอาหารยามสงครามเป็นกำหนดการเชิงเส้น (linear programming) อันเดียวกันที่ใส่เสื้อผ้าคนละชุด — เว้นแต่ตรงนี้การรู้จำเฉือนไปคนละทาง การลดรูปไม่ได้พบทางลัด แต่พิสูจน์ได้ว่าไม่มีทางลัดใดเป็นไปได้ ด้วยการแสดงว่าปัญหาของคุณยากอย่างน้อยเท่ากับปัญหาที่รู้กันแล้วว่าต้านทานความพยายามหาทางลัดทุกครั้ง
หอผู้ร้ายของ Karp
ทฤษฎีบทของ 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 อ่านเหมือนทัวร์คณิตศาสตร์ประยุกต์: กราฟหนึ่งระบายสีด้วยจำนวนสีที่กำหนด โดยไม่ให้โหนดสองโหนดที่เชื่อมกันใช้สีเดียวกัน ได้หรือไม่; ชุดของสิ่งของหนึ่งแบ่งเป็นสองกองที่มีมูลค่ารวมเท่ากันได้หรือไม่; เครือข่ายหนึ่งถูกครอบคลุมด้วยชุดโหนดที่เลือกมาไม่กี่โหนดที่แตะทุกเส้นเชื่อมได้หรือไม่; สูตรตรรกะแบบบูลในรูปจำกัดรูปหนึ่งสอดคล้องได้หรือไม่ นักทฤษฎีกราฟ นักวิจัยดำเนินงาน และนักตรรกวิทยาโจมตีปัญหาเหล่านี้แยกกัน และไม่มีเหตุผลอะไรเป็นพิเศษให้คิดว่าความยากลำบากของแต่ละฝ่ายเชื่อมโยงกัน โซ่การลดรูปของ Karp เผยว่าทั้งหมดคือโรคเดียวกันที่สวมเครื่องแต่งกายยี่สิบเอ็ดชุด — การค้นพบแบบเดียวกับที่บทที่ 04 เฉลิมฉลองในไม้อัดของ Kantorovich และสูตรอาหารของ Stigler พอดี เว้นแต่ว่าตรงนี้อัตลักษณ์ร่วมคือ*คำสาป*ร่วม ไม่ใช่ทางลัดร่วม พบอัลกอริทึมที่มีประสิทธิภาพสำหรับข้อใดข้อหนึ่ง ก็เท่ากับพบสำหรับทุกข้อ และสำหรับทุกปัญหาใน NP ด้วย ไม่เคยมีใครพบ ไม่เคยมีใครพิสูจน์ว่าไม่มีใครพบได้ ช่องว่างนั้น — ระหว่างความพยายามที่ล้มเหลวมาหลายทศวรรษ กับบทพิสูจน์ความเป็นไปไม่ได้อย่างเข้มงวด — คือที่ที่คำถามรางวัลมิลเลนเนียมอาศัยอยู่พอดี
คำถามหนึ่งล้านดอลลาร์
ปี 2000 Clay Mathematics Institute เลือกปัญหาเจ็ดข้อที่ตัดสินว่าเป็นคำถามเปิดที่ลึกที่สุดในคณิตศาสตร์ และตั้งรางวัลหนึ่งล้านดอลลาร์ให้คำตอบที่ถูกต้องคำตอบแรกของแต่ละข้อ P versus NP เป็นหนึ่งในเจ็ดข้อนั้น — พูดอย่างเป็นทางการคือ ปัญหาทุกข้อที่*ตรวจสอบ*คำตอบได้อย่างมีประสิทธิภาพ ยอมให้มีวิธี*ค้นพบ*ที่มีประสิทธิภาพด้วยหรือไม่ — และ ณ เวลาที่เขียนอยู่นี้ยังไม่มีใครแก้ได้ มันเป็นหนึ่งในหกข้อจากเจ็ดข้อเดิมที่ยังยืนอยู่; มีเพียงข้อความคาดการณ์ Poincaré เท่านั้นที่ล้มลง โดยฝีมือของ Grigori Perelman ช่วงต้นทศวรรษ 2000 (Clay Mathematics Institute, "P vs NP"; Wikipedia, "Millennium Prize Problems")
ปัญหาพนักงานขายเดินทาง (traveling salesman problem) กลายเป็นสัญลักษณ์ของบทนี้ ด้วยเหตุผลที่ดี: มันง่ายพอจะเล่าให้เด็กฟัง (หาเส้นทางที่สั้นที่สุดเท่าที่จะเป็นไปได้ ที่แวะทุกเมืองในรายการเมืองละครั้งพอดีแล้วกลับบ้าน) และยากพอจนไม่เคยมีใครหาวิธีแก้มันแบบตรงเป๊ะสำหรับอินสแตนซ์ขนาดใหญ่ ที่ชนะการลองด้วยปริมาณงานที่โตระเบิดตามจำนวนเมืองได้ มันนั่งอยู่ข้างๆ SAT และยี่สิบเอ็ดข้อของ Karp บนอีกฟากของกำแพง — ไม่มีใครพิสูจน์ว่ามันแก้เร็วไม่ได้ แต่มีบทพิสูจน์ว่ามันยากเท่ากับปัญหาอื่นทุกข้อในตระกูลมหึมาที่ยังไม่มีข้อยุติตระกูลเดียวกัน เป๊ะๆ
"กำแพง" อ้างอะไรกันแน่ ควรหยุดพูดตามตรงสักครู่ เพราะมันเผลออ้างเกินจริงได้ง่าย ไม่มีใครพิสูจน์ว่า P ≠ NP ยังเป็นไปได้ในเชิงตรรกะ — แม้แทบไม่มีนักวิทยาการคอมพิวเตอร์คนไหนเชื่อ — ว่าอัลกอริทึมอันชาญฉลาดสักตัวสำหรับ SAT กำลังรอให้ค้นพบอยู่ และการพบมันจะแก้ทุกปัญหาในรายการของ Karp และทุกปัญหาแบบเดียวกันได้อย่างมีประสิทธิภาพในคราวเดียว สิ่งที่พิสูจน์แล้วอย่างเข้มงวดเต็มที่คือ*ความสมมูล*: แก้สมาชิกหนึ่งตัวของตระกูลมหึมานี้ได้อย่างมีประสิทธิภาพ ก็เท่ากับแก้ได้ทั้งตระกูล กำแพงนี้จะถาวรหรือไม่ ยังไม่มีใครรู้ สิ่งที่แน่คือมันเป็นกำแพงเดียวกัน ไม่ว่าจะไปดันตรงไหน
ชีวิตที่เชิงกำแพง
ถ้าทฤษฎีหยุดอยู่แค่นี้ บทนี้ก็เป็นบทว่าด้วยความสิ้นหวัง: บทพิสูจน์ว่าปัญหาสำคัญในทางปฏิบัติจำนวนมากแก้แบบตรงเป๊ะและมีประสิทธิภาพไม่ได้ จบ สิ่งที่เกิดขึ้นจริงต่อจากนั้นน่าสนใจกว่า และมันคือส่วนของเรื่องเล่าในบทนี้ที่ทำให้ข้อเสนอใจกลางของหนังสือเล่มนี้ยังมีชีวิตอยู่แม้ในจุดที่มืดที่สุด — เพราะนักแก้ปัญหาที่เจอกำแพงไม่ได้หยุด พวกเขาหาประตูเจอ
ประตูบานแรกคือการประมาณ (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") อัลกอริทึมประมาณไม่ได้เอาชนะกำแพง มันเจรจาเงื่อนไขกับกำแพง: ไม่ใช่คำตอบที่ดีที่สุด แต่เป็นคำตอบที่*พิสูจน์ได้*ว่าดีพอ ส่งมอบในเวลาที่ไม่ระเบิด
ประตูบานที่สองคือการสุ่ม (randomization) — ความเต็มใจแลกความแน่นอนกับความเร็วแบบเดียวกับที่บทที่ 04 พบในวิธีมอนติคาร์โล คราวนี้ใช้กับการค้นหาเชิงการจัดหมู่แทนการจำลองทางกายภาพ อัลกอริทึมแบบสุ่มตัดสินใจบางส่วนด้วยการโยนเหรียญแทนการเทียบทุกทางเลือก สำหรับปัญหายากหลายข้อ วิธีนี้ให้อัลกอริทึมที่เร็วโดยเฉลี่ยและผิดด้วยความน่าจะเป็นที่ควบคุมได้และเล็กจนแทบหายไป — แลกคำตอบที่รับประกันว่าถูก กับคำตอบที่แทบจะแน่นอนว่าถูกและมาถึงเร็วกว่ามาก ตัวอย่างในชีวิตประจำวันที่ชัดที่สุดอยู่ในวิทยาการรหัสลับที่บทนี้กำลังจะหันไปพูดถึงพอดี และก็เหมาะเจาะดี: ก่อน RSA จะล็อกอะไรได้ มันต้องมีจำนวนเฉพาะขนาดใหญ่มากสองจำนวนก่อน และการทดสอบว่าจำนวนมหึมาที่เป็นตัวเลือกเป็นจำนวนเฉพาะหรือไม่ด้วยการหารไล่ ตัวมันเองก็ช้าจนหมดหวัง การทดสอบ Miller–Rabin ที่ Gary Miller คิดขึ้นในปี 1976 และ Michael Rabin ทำให้ใช้งานได้จริงเต็มที่ในเวลาไม่นานหลังจากนั้น เลือกพยานแบบสุ่มขึ้นมาแล้วตรวจแต่ละตัวกับจำนวนที่เป็นตัวเลือก; พยานสุ่มตัวเดียวจับจำนวนประกอบได้ด้วยโอกาสอย่างน้อยครึ่งต่อครึ่ง ดังนั้นหลังจับพยานอิสระห้าสิบตัว โอกาสได้คำตอบผิดตกลงต่ำกว่าหนึ่งในพันล้านล้าน — เล็กพอจนกุญแจ RSA ทุกดอกที่สร้างขึ้นทุกวันนี้ตั้งอยู่บนจำนวนเฉพาะที่ผ่านการทดสอบที่พูดอย่างเคร่งครัดแล้วไม่ได้แน่นอน แค่แน่นอนพอ (Cornell CS4820, "The Miller-Rabin Randomized Primality Test")
ประตูบานที่สามน่าประหลาดใจที่สุด และเป็นบานที่คอมพิวเตอร์สมัยใหม่เดินผ่านเงียบๆ ทุกวันโดยที่ผู้ใช้ส่วนใหญ่ไม่เคยสังเกต ในหลายทศวรรษหลังทฤษฎีบทของ 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) บอกว่าควรจะแตะไม่ได้ กำแพงนั้นเป็นของจริง ในกรณีเลวร้ายที่สุด สำหรับทุกอินสแตนซ์ที่ใครก็ตามจะสร้างขึ้นได้ และสำหรับอินสแตนซ์ที่โผล่มาในทางปฏิบัติจริงๆ มันก็เต็มไปด้วยประตูที่ไม่มีใครทำนายว่าจะอยู่ตรงนั้น
กำแพงในฐานะป้อมปราการ
จุดหักครั้งสุดท้ายในเรื่องเล่าของบทนี้กลับทุกอย่างที่มาก่อนหน้า และเป็นการกลับด้านที่ส่งผลมากที่สุดในหนังสือเล่มนี้ นักแก้ปัญหาทุกคนจนถึงตอนนี้ปฏิบัติกับความยาก (hardness) เหมือนอุปสรรค: กำแพงที่ต้องลดรูปหนีออกมา ประมาณอ้อมไป หรือสุ่มทะลุผ่าน ปี 1977 นักวิจัย MIT สามคน — Ron Rivest, Adi Shamir และ Leonard Adleman — ตระหนักว่าความยากเป็น*ตัวสินค้า*ได้แทน
ระบบรหัสลับของพวกเขา คือ RSA ใช้อักษรย่อของนักวิจัยทั้งสามเป็นชื่อ และสร้างขึ้นบนอินสแตนซ์ของความยากเชิงการคำนวณที่เจาะจงและเลือกมาอย่างพิถีพิถัน: คูณจำนวนเฉพาะขนาดใหญ่มากสองจำนวนเข้าด้วยกันนั้นเร็ว คอมพิวเตอร์ใช้เวลาเสี้ยววินาทีแม้กับจำนวนที่ยาวหลายร้อยหลัก แต่การ*แยกตัวประกอบ*ผลคูณที่ได้กลับไปเป็นจำนวนเฉพาะสองจำนวนตั้งต้น โดยไม่รู้มันอยู่ก่อน ไม่มีวิธีที่มีประสิทธิภาพที่รู้จักเลย — กลับไปสู่อะไรที่คล้ายการค้นหาแบบไล่ทุกทาง (brute force) ผ่านพื้นที่ของตัวประกอบที่เป็นไปได้ที่ใหญ่ระดับดาราศาสตร์ (Splunk, "RSA Algorithm in Cryptography: Rivest Shamir Adleman Explained") ใครก็ประกาศผลคูณนั้นได้ — "กุญแจสาธารณะ" — และใช้มันล็อกข้อความ มีเพียงคนที่รู้จำนวนเฉพาะตั้งต้นสองจำนวน — "กุญแจส่วนตัว" — เท่านั้นที่ปลดล็อกได้อย่างมีประสิทธิภาพ; คนอื่นทั้งหมดเจอกำแพงเชิงการคำนวณที่เป็นของจริงพอๆ กับกำแพงของพนักงานขายเดินทาง ในทางเทคนิค เชื่อกันว่า RSA พึ่งความยากของการแยกตัวประกอบจำนวนเต็ม มากกว่าจะมีบทพิสูจน์ว่าเป็น NP-complete ในความหมายเคร่งครัดแบบ Cook–Levin — การแยกตัวประกอบนั่งอยู่ในมุมที่แปลกและยังไม่มีข้อยุติเต็มที่ของทฤษฎีความซับซ้อน ดูจะยาก แต่ไม่มีใครรู้ว่าตัวมันเองเป็น NP-complete หรือไม่ สิ่งที่สำคัญสำหรับเป้าหมายของบทนี้คือบานพับทางปรัชญา ไม่ใช่ตัวหนังสือตัวเล็กเชิงเทคนิค: คณิตศาสตร์ประยุกต์ทั้งสาขาค้นพบว่ากำแพงที่ไม่มีใครปีนได้ มีค่าเท่ากับสมบัติที่ไม่มีใครขโมยได้พอดี ทุกการเชื่อมต่อที่ปลอดภัยไปยังธนาคาร เวชระเบียนของโรงพยาบาล หรือข้อความที่เข้ารหัส ล้วนตั้งอยู่บนความยากชนิดเดียวกันกับที่ทำให้ปัญหาพนักงานขายเดินทางต้านทานความฉลาดของนักแก้ปัญหาทุกคน ทางตันของสาขาหนึ่งคือรากฐานของอีกสาขาหนึ่ง
ความยากคือข้อมูล
บทนี้ปิดสิ่งที่บทที่ 00 สัญญาไว้ และบทที่ 04 กับ 05 ปูทางมาถึง: ขีดจำกัดที่ซื่อสัตย์ของข้ออ้างใจกลางของหนังสือเล่มนี้ ถอยออกมามองจะเห็นชัด "นักแก้ปัญหาที่ยิ่งใหญ่ไม่ค้นหาหนักขึ้น — เขาเปลี่ยนพื้นที่จนเส้นทางสั้นลง" ยืนอยู่ได้ตลอดทุกบทที่ผ่านมา — จุดของ Euler กองเรือคุ้มกันของ Blackett แนวหน้าของ Dijkstra การมองโลกในแง่ดีแบบ admissible ของ A\* NP-completeness คือบทพิสูจน์ของเล่มนี้ว่าข้ออ้างนั้นมีขอบเขตจริง พื้นที่บางแบบบีบอัดไม่ได้ด้วยการเปลี่ยนรูปแบบการแทนปัญหา (representation) ใดๆ ไม่ว่าจะฉลาดแค่ไหน เท่าที่ใครเคยพิสูจน์ได้หรือน่าจะพิสูจน์ได้ในเร็ววัน เหตุผลไม่ใช่ว่ายังไม่มีใครฉลาดพอ Cook, Levin และ Karp แสดงให้เห็นว่าถ้าบีบอัดพื้นที่*ข้อใดข้อหนึ่ง*ได้อย่างมีประสิทธิภาพ ก็จะบีบอัด*ทุกข้อ*ได้อย่างมีประสิทธิภาพไปด้วย และเจ็ดสิบปีที่สมองดีที่สุดในวิทยาการคอมพิวเตอร์พยายามทำเรื่องนั้นพอดี ก็กลับมามือเปล่า
แต่ให้สังเกตว่าความล้มเหลวนั้นเป็นความรู้ชนิดไหนกันแน่ การรู้ว่าปัญหาข้อหนึ่งอยู่หลังกำแพง NP-complete ไม่ใช่การไม่มีคำตอบ — มันคือ*ชิ้นข้อมูลเกี่ยวกับปัญหานั้น* เป็นรูปธรรมและใช้ได้จริงพอๆ กับการรู้ขนาดหรือความสมมาตรของมัน มันบอกทันทีว่าอย่าผลาญทั้งอาชีพไปกับการล่าอัลกอริทึมที่ตรงเป๊ะและเร็วเสมอ มันบอกให้เอื้อมไปหาการประมาณ การสุ่ม หรือตัวแก้ที่สร้างมาเพื่อใช้ประโยชน์จากโครงสร้างในโลกจริงเท่าที่อินสแตนซ์ของคุณมีอยู่จริง แทนกรณีเลวร้ายที่สุดในทางทฤษฎีของมัน และในกรณีของ RSA มันบอกว่ากำแพงที่ยังยืนอยู่อาจมีค่ามากกว่ากำแพงที่ถูกทุบลง การเรียกชื่อกำแพงเป็นการแก้ปัญหาในตัวมันเอง — มันคือการเปลี่ยน representation ครั้งสุดท้ายและได้มายากที่สุดที่ส่วนนี้ของหนังสือมีให้: เปลี่ยนกรอบ "ฉันหาอัลกอริทึมที่เร็วไม่ได้" จากความล้มเหลวส่วนตัว ให้เป็นข้อเท็จจริงเชิงโครงสร้างที่พิสูจน์แล้วเกี่ยวกับพื้นที่ แล้วเลือกด้วยตาที่เปิดกว้างว่าจะเดินผ่านประตูบานไหนแทน
ท่าประจำบท
Move 06 — เรียกชื่อกำแพง แล้วแลก: ลดรูป ประมาณ สุ่ม หรือเอาความยากไปใช้ประโยชน์
- ก่อนจะค้นหาอยู่หลายปี ตรวจก่อนว่าปัญหาของคุณคือสัตว์ประหลาดที่รู้จักกันดีซึ่งปลอมตัวมาหรือเปล่า การลดรูปจากปัญหาในรายการของ Karp หรือจาก SAT เอง คือหลักฐานว่าไม่มีใครอื่นหาคำตอบทั่วไปที่เร็วเจอเหมือนกัน — เรื่องนี้ควรรู้ก่อน ไม่ใช่หลัง ความพยายามที่ล้มเหลวคุ้มค่าทั้งอาชีพ
- เมื่อตรงเป๊ะกับเร็วมีพร้อมกันไม่ได้ จงเลือกอย่างตั้งใจว่าจะสละอันไหน ขอบเขตของ Christofides แลกความตรงเป๊ะกับการประมาณที่รับประกันว่าดี; การสุ่มแบบมอนติคาร์โลแลกความแน่นอนกับความน่าจะเป็นที่ท่วมท้น ทั้งคู่คือการตัดสินใจเชิงวิศวกรรม ไม่ใช่ความพ่ายแพ้
- ตรวจว่าอินสแตนซ์จริงของคุณคือกรณีเลวร้ายที่สุดที่ถูกออกแบบมาเล่นงาน หรือกรณีทั่วไปที่เป็นมิตร SAT solver แบบ CDCL พิสูจน์ว่า "NP-complete ในทางทฤษฎี" กับ "จัดการไม่ไหว (intractable) ในข้อมูลเฉพาะของคุณ" เป็นคนละข้ออ้างกัน; SAT ระดับอุตสาหกรรมคือหลักฐานว่าปัญหาจริงมักใจดีกว่าทฤษฎีบทที่ตีกรอบมันไว้มาก
- ถามว่าความยากนั้นเองมีค่าหรือไม่ RSA แสดงให้เห็นว่ากำแพงที่ไม่มีใครปีนได้ เปลี่ยนเป็นป้อมปราการได้ ก่อนจะปฏิบัติกับความจัดการไม่ไหวเหมือนอุปสรรคล้วนๆ ให้ถามว่าใครจะยอมจ่ายเงินซื้อปัญหาที่ยากอยู่อย่างนั้นตลอดไป
ต่อไป — บทที่ 07 · หอเรื่องเล่า I: ท่าเดียวจบ: ทฤษฎีถึงคราวหลีกทางให้หอเรื่องเล่า นักแก้ปัญหาห้าคน สี่ศตวรรษ คนละหนึ่งท่า — ประวัติศาสตร์ที่หนังสือเล่มนี้ก่อไว้ในเชิงนามธรรม ถูกทำให้เป็นรูปธรรม ทีละการแก้ครั้งใหญ่
บทถัดไป · 8 / 1207 · หอเรื่องเล่า I: ท่าเดียวจบ