10 · ความซับซ้อน
การไต่สวนครั้งที่สองของภาค II บทที่ 09 ถามว่าการคำนวณทำอะไรได้บ้างในหลักการ บทนี้ถามว่ามันทำอะไรได้ก่อนเอกภพจะหมดความอดทน — และคำถามที่สองนั้นเป็นแค่เรื่องเชิงปฏิบัติ หรือคมลึกเท่ากับข้อแบ่งแยกใดๆ ที่ปรัชญาเคยขีดไว้
"เป็นไปได้ในหลักการแต่ไม่เป็นไปได้ในทางปฏิบัติ" นับเป็นหมวดหมู่เชิงอภิปรัชญาหรือไม่?
Boolean satisfiability มีคุณสมบัติประหลาดข้อหนึ่ง: ทุกปัญหาที่คำตอบเสนอมาแล้ว*ตรวจสอบ*ได้เร็ว ล้วนลดรูปมาเป็นมันได้หมด Stephen Cook พิสูจน์ข้อนี้ในบทความ "The Complexity of Theorem-Proving Procedures" ที่เสนอต่องาน ACM Symposium on Theory of Computing ครั้งที่สาม เดือนพฤษภาคม 1971 — โจทย์คือให้สูตรตรรกะมาหนึ่งสูตร แล้วถามว่ามีการกำหนดค่าจริง/เท็จให้ตัวแปรแบบใดแบบหนึ่งที่ทำให้สูตรเป็นจริงหรือไม่ สองปีต่อมา Leonid Levin พิสูจน์ทฤษฎีบทเดียวกันเป๊ะในสหภาพโซเวียต ถูกตัดขาดจากวารสารตะวันตก ไม่เคยเห็นบทความของ Cook — การลู่เข้าหากันโดยอิสระครั้งที่สองสู่ผลลัพธ์เดียวกัน รูปทรงเดียวกับ Church และ Turing เมื่อสามสิบห้าปีก่อนหน้า บทความของ Richard Karp ปี 1972 เรื่อง "Reducibility Among Combinatorial Problems" ตามมาชี้ว่าปัญหายากที่คุ้นหน้ากันดี 21 ปัญหา — พนักงานขายเดินทาง (travelling salesman), การระบายสีกราฟ, คลีค (clique) — ล้วนเป็น satisfiability ที่แปลงร่างมา Cook, Levin และ Karp ระบุรอยแยกเดียวกันได้: P คือคลาสของปัญหาที่แก้ได้เร็ว ส่วน NP คือคลาสที่คำตอบตรวจสอบได้เร็วเมื่อหาเจอแล้ว P เท่ากับ NP หรือไม่ คือคำถามเปิดที่สะเทือนมากที่สุดในคณิตศาสตร์ และผู้เชี่ยวชาญแทบทุกคนเชื่อว่าคำตอบคือไม่เท่า
ปรัชญาโละเรื่องนี้ทิ้งเป็นรายละเอียดทางวิศวกรรมไม่ได้ แถลงการณ์ปี 2011 ของ Scott Aaronson เรื่อง "Why Philosophers Should Care About Computational Complexity" โต้แย้งไว้อย่างนั้น ตรรกศาสตร์เชิงญาณ (epistemic logic) แบบคลาสสิกสมมติผู้กระทำที่เชื่อผลสืบเนื่องเชิงตรรกะทุกข้อของสิ่งที่ตนเชื่อ — ความรอบรู้เชิงตรรกะ (logical omniscience) — และถือว่าข้อสมมตินี้เป็นอุดมคติ แบบที่ฟิสิกส์อุดมคติระนาบไร้แรงเสียดทาน ทฤษฎีความซับซ้อนชี้ว่ามันไม่ใช่อุดมคติ แต่เป็นไปไม่ได้: ความเชื่อธรรมดาจำนวนมาก ถ้าจะอนุมานผลสืบเนื่องให้ครบทุกข้อ ต้องใช้เวลานานเกินอายุเอกภพ ต่อให้ยกคอมพิวเตอร์ทุกเครื่องที่มนุษยชาติสร้างได้มาให้หมดก็ตาม Aaronson ส่องเลนส์เดียวกันนี้ไปที่ปัญหาการอุปนัยของ Hume ปัญหาของ Newcomb และเหตุผลเชิงเศรษฐศาสตร์ — ทุกกรณี ปริศนาที่ดูเป็นเรื่องมโนทัศน์ล้วนๆ กลับมีโครงเชิงคำนวณซ่อนอยู่ข้างในที่ไม่มีใครเคยตีราคาไว้
โครงนั้นเห็นชัดที่สุดในสิ่งที่ P vs NP บอกเกี่ยวกับความคิดสร้างสรรค์ การตรวจซูโดกุที่เติมเสร็จแล้ว หรือบทพิสูจน์ทางคณิตศาสตร์ที่เสนอมา ใช้แรงงานเท่าเดิมและไม่มาก ไม่ว่าคำตอบนั้นจะได้มาอย่างไร แต่การไล่ค้นปริภูมิของการจัดเรียงที่เป็นไปได้ทั้งหมด หรือบทพิสูจน์ที่เป็นไปได้ทั้งหมด — ถ้า P ≠ NP — ยากขึ้นแบบยกกำลัง (exponentially) ในกรณีเลวร้ายที่สุด จัดระเบียบการค้นให้ฉลาดแค่ไหนก็ไม่ช่วย ประกายความเข้าใจของนักคณิตศาสตร์ วินาทีที่กลยุทธ์การพิสูจน์ผุดขึ้นมาเอง อาจกำลังทำสิ่งที่ไม่มีอัลกอริทึมเชิงระบบใดแทนได้: จำได้ว่าถูกนั้นถูก หามันเจอนั้นแพง และระยะห่างระหว่างสองอย่างนี้คือสิ่งที่ทฤษฎีความซับซ้อนวัดพอดี หมากรุกให้ตัวอย่างที่เก่ากว่าและบริสุทธิ์กว่าของช่องว่างเดียวกัน Ernst Zermelo พิสูจน์ในปี 1913 ว่าหมากรุก*ถูกกำหนดผลไว้แล้ว* (determined) — หนึ่งในสามข้อ "ขาวบังคับให้ชนะได้" "ดำบังคับให้ชนะได้" หรือ "ทั้งสองฝ่ายบังคับได้อย่างน้อยที่สุดคือเสมอ" เป็นจริงแน่นอน เพราะต้นไม้เกม (game tree) ของมันจำกัด ไม่มีใครรู้ว่าข้อไหน เพราะ "จำกัด" กับ "ค้นหาได้ทั่วถึง" เป็นข้อกล่าวอ้างคนละเรื่อง ต้นไม้เกมใหญ่เกินกว่าอุปกรณ์ใดๆ ที่ใครคาดหวังว่าจะสร้างขึ้นได้จะวิเคราะห์ครบทุกกรณี "แก้ได้ในหลักการ" กับ "จริง" ห่างกันมากกว่าที่คำสองคำนั้นบอกเป็นนัย
Herbert Simon เห็นช่องว่างนี้จากอีกด้าน หลายทศวรรษก่อนทฤษฎีความซับซ้อนจะวัดมันได้ หนังสือ Administrative Behavior (1947) และบทความ "A Behavioral Model of Rational Choice" (Quarterly Journal of Economics 69, 1955: 99–118) ของเขาถอดผู้กระทำแบบคลาสสิก — ผู้สำรวจตัวเลือกและผลลัพธ์ทุกข้อก่อนเลือกตัวที่ดีที่สุด — ออก แล้วใส่ผู้กระทำแบบ satisficing (การพอใจแค่พอ) เข้าไปแทน คนที่หยุดตรงตัวเลือกแรกที่ผ่านเกณฑ์ "ดีพอ" Simon ตั้งใจให้นี่เป็นจิตวิทยา เป็นคำอธิบายว่าผู้จัดการและคนซื้อของตัดสินใจกันจริงๆ อย่างไร ทฤษฎีความซับซ้อนมาทีหลังและวางพื้นให้มันใหม่ พื้นที่ไม่เกี่ยวกับจิตวิทยาเลย ผู้กระทำใดก็ตามที่ทำงานใต้งบเวลาจริง — มนุษย์ บริษัท หรืออัลกอริทึม — เป็นผู้กระทำที่มีเหตุผลมีขอบเขต (bounded rationality) โดยความจำเป็นทางกายภาพ อยากเป็นหรือไม่อยากก็ตาม
รอยแยกเดียวกันนั้น เมื่อถูกใช้เป็นทรัพยากรแทนที่จะเป็นอุปสรรค สร้างวิทยาการเข้ารหัสสมัยใหม่ขึ้นมา บทความ "New Directions in Cryptography" ของ Whitfield Diffie และ Martin Hellman (IEEE Transactions on Information Theory 22, 1976: 644–654) เสนอว่าฟังก์ชันประตูกลทางเดียว (trapdoor one-way function) — คำนวณไปข้างหน้าง่าย ผกผันกลับโดยไม่มีกุญแจลับแทบเป็นไปไม่ได้ในเชิงคำนวณ — จะทำให้คนแปลกหน้าสองคนตกลงความลับร่วมกันผ่านช่องทางเปิดได้ ตัวบทความเองไม่มีตัวอย่างที่ใช้งานจริงเสนอไว้ RSA ให้ตัวอย่างนั้นในเวลาไม่นานต่อมา: การคูณจำนวนเฉพาะสามร้อยหลักสองตัวกินเวลาโปรเซสเซอร์ระดับมิลลิวินาที ส่วนการแยกตัวประกอบผลคูณกลับเป็นจำนวนเฉพาะเดิม เชื่อกันว่าทุกวิธีที่รู้จักจะใช้เวลานานกว่าอายุของเอกภพ ไอคอนแม่กุญแจทุกอันบนเบราว์เซอร์วางอยู่บนข้อคาดการณ์เชิงความซับซ้อนที่ยังพิสูจน์ไม่ได้ ไม่ได้วางอยู่บนบทพิสูจน์ — ฟังก์ชันทางเดียว (one-way function) คือฟิสิกส์ประยุกต์ของการเก็บความลับ ตามความหมายตรงตัวเป๊ะๆ
ลูกที่แปลกที่สุดของทฤษฎีความซับซ้อนรื้อนิยามของคำว่า "บทพิสูจน์" ใหม่ทั้งอัน บทความ "The Knowledge Complexity of Interactive Proof-Systems" ของ Shafi Goldwasser, Silvio Micali และ Charles Rackoff (17th ACM Symposium on Theory of Computing, Providence, 1985; ฉบับเต็มใน SIAM Journal on Computing 18, 1989: 186–208) แสดงว่าผู้พิสูจน์ (prover) โน้มน้าวผู้ตรวจสอบ (verifier) ให้เชื่อว่าข้อความหนึ่งเป็นจริงได้ — "กราฟสองอันนี้ isomorphic กัน" "ฉันรู้รหัสผ่าน" — ผ่านการโต้ตอบไปมาแบบสด และบันทึกบทสนทนาของการโต้ตอบนั้น เมื่อคนที่ไม่ได้ร่วมแลกเปลี่ยนมาอ่านย้อนหลัง พิสูจน์อะไรไม่ได้เลยสักอย่าง น้ำหนักเชิงหลักฐานอยู่ที่การซักถามสด (live interrogation) และความน่าจะเป็นที่หดลงเรื่อยๆ ของการปล่อยคนโกงลอดผ่าน ไม่ได้อยู่ที่วัตถุนิ่งที่ใครจะหยิบมาตรวจย้อนหลังได้ นั่นแตกหักกับบทพิสูจน์ทุกชิ้นนับแต่ Euclid เป็นต้นมา ที่บทพิสูจน์คือของตายตัวซึ่งยื่นให้ใครคนหนึ่งไปตรวจเองตามลำพัง ตรงนี้ปรัชญามีเหตุผลจะคัดค้านว่าการคำนวณนิยาม "บทพิสูจน์" ใหม่ให้เหลือแค่เรื่องเชิงสถิติ คำตอบตรงไปตรงมาของทฤษฎีความซับซ้อนคือ ภาพความแน่นอนแบบเก่านั้นไม่เคยมีจริงในระดับใหญ่มาตั้งแต่ต้น — บทที่ 12 จะปิดข้อโต้แย้งนี้ให้จบ
"เป็นไปได้ในหลักการแต่ไม่เป็นไปได้ในทางปฏิบัติ" จะสมควรได้ชื่อว่าเชิงอภิปรัชญาหรือไม่ ขึ้นอยู่กับว่าเส้นขอบนั้นตายตัว หรือเป็นแค่เรื่องเชิงประวัติศาสตร์ คลาสความซับซ้อน (complexity class) แบบกรณีเลวร้ายที่สุดเป็นข้อเท็จจริงทางคณิตศาสตร์ แต่ตัวอย่างจริงไม่ได้เป็นกรณีเลวร้ายที่สุดเสมอไป: ตัวแก้ SAT เชิงปฏิบัติทุกวันนี้ปิดคำถาม satisfiability ที่มีตัวแปรเป็นล้านตัวได้ ทั้งที่ทฤษฎีเรียกมันว่าแก้ไม่ได้ในทางปฏิบัติ (intractable) เพราะสูตรจริงส่วนใหญ่อยู่ไกลจากตัวอย่างปฏิปักษ์ (adversarial examples) ที่บทพิสูจน์เหล่านั้นสร้างขึ้นบนฐานของมัน ช่องว่างระหว่าง "P ≠ NP" กับ "ปัญหาข้อนี้โดยเฉพาะ วันนี้ บนฮาร์ดแวร์นี้ อยู่นอกเอื้อม" คือจุดที่สังคมวิทยาและวิศวกรรมทำงานเงียบๆ แทนสิ่งที่ทฤษฎีความซับซ้อนล้วนๆ ยังรับรองไม่ได้
เชื่อมโยง
บทที่ 09 วางไว้ว่าการคำนวณทำอะไรได้บ้างในหลักการ บทนี้วัดว่ามันทำอะไรได้ภายในเวลาที่มีจำกัด บทที่ 03 ถามว่าคำให้การของเครื่องจักรนับเป็นความรู้หรือไม่ interactive proof คือคำถามข้อนั้นที่ติดความน่าจะเป็นมาด้วย บทที่ 06 เจอรูปแบบผลลัพธ์ความเป็นไปไม่ได้แบบเดียวกันในความเป็นธรรมเชิงอัลกอริทึม (algorithmic fairness) บทที่ 11 รับช่วงต่อด้วย Kolmogorov complexity ญาติของความซับซ้อนเชิงคำนวณที่วัดความยาวคำอธิบายแทนเวลาในการรัน
คำถามที่ยังเปิดอยู่
ถ้า P vs NP ถูกคลี่คลายพรุ่งนี้ มันยุติคำถามเชิงอภิปรัชญา หรือยุติแค่คำถามเชิงคณิตศาสตร์? ช่องว่างระหว่างความยากแบบกรณีเลวร้ายที่สุดกับความแก้ได้จริงในโลกจริง แปลว่าคลาสความซับซ้อนอธิบายโลก หรืออธิบายแค่ปฏิปักษ์ที่นักคณิตศาสตร์เลือกจะจินตนาการขึ้นมา? และถ้าเหตุผลมีขอบเขต (bounded rationality) เป็นความจำเป็นทางกายภาพของผู้กระทำทุกราย ภาพคลาสสิกของผู้สังเกตการณ์ในอุดมคติที่มีเหตุผลเต็มเปี่ยม ภาพที่ปรัชญาสร้างทฤษฎีความรู้และการเลือกขึ้นมาบนมัน ยังเหลืออะไรอยู่?
อ่านต่อ
- Scott Aaronson, Quantum Computing Since Democritus (Cambridge: Cambridge University Press, 2013).
- Stephen Cook, "The Complexity of Theorem-Proving Procedures," Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971): 151–158; Scott Aaronson, "Why Philosophers Should Care About Computational Complexity" (2011) — arxiv.org/abs/1108.1791.
- Stanford Encyclopedia of Philosophy, "Computational Complexity Theory" — plato.stanford.edu/entries/computational-complexity.