10 · Complexity
10 · ความซับซ้อน
Second hearing of Part II. Chapter 09 asked what computation can do at all; this one asks what it can do before the universe runs out of patience — and whether that second question is merely practical or cuts as deep as any distinction philosophy has drawn.
การไต่สวนครั้งที่สองของภาค II บทที่ 09 ถามว่าการคำนวณทำอะไรได้บ้างในหลักการ บทนี้ถามว่ามันทำอะไรได้ก่อนเอกภพจะหมดความอดทน — และคำถามที่สองนั้นเป็นแค่เรื่องเชิงปฏิบัติ หรือคมลึกเท่ากับข้อแบ่งแยกใดๆ ที่ปรัชญาเคยขีดไว้
Is "possible in principle but not in practice" a metaphysical category?
"เป็นไปได้ในหลักการแต่ไม่เป็นไปได้ในทางปฏิบัติ" นับเป็นหมวดหมู่เชิงอภิปรัชญาหรือไม่?
In May 1971, at the third ACM Symposium on Theory of Computing, Stephen Cook presented "The Complexity of Theorem-Proving Procedures," proving that Boolean satisfiability — given a formula, does some assignment of true/false to its variables make it true? — has a peculiar property: every problem whose proposed solutions can be checked quickly reduces to it. Two years later, cut off from Western journals, Leonid Levin proved the identical theorem in the Soviet Union without having seen Cook's paper — a second independent convergence on the same result, the same shape as Church and Turing thirty-five years earlier. Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems" then showed that twenty-one familiar hard problems — the travelling salesman, graph coloring, clique — are all satisfiability in disguise. Cook, Levin, and Karp had located a single fault line: P, the class of problems solvable quickly, against NP, the class whose solutions can be checked quickly once found. Whether P equals NP is the most consequential open question in mathematics, and almost every expert believes the answer is no.
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 หรือไม่ คือคำถามเปิดที่สะเทือนมากที่สุดในคณิตศาสตร์ และผู้เชี่ยวชาญแทบทุกคนเชื่อว่าคำตอบคือไม่เท่า
Scott Aaronson's 2011 manifesto "Why Philosophers Should Care About Computational Complexity" argues that this is not a technicality philosophy can set aside as an engineering detail. Classical epistemic logic assumes an agent who believes all the logical consequences of what she believes — logical omniscience — and treats the assumption as an idealization, the way physics idealizes frictionless planes. Complexity theory shows it is not an idealization but an impossibility: for many ordinary beliefs, deriving every consequence would outlast the universe even granted every computer humanity could ever build. Aaronson extends the same lens to Hume's problem of induction, to Newcomb's problem, and to economic rationality — in each case, a puzzle that looked purely conceptual turns out to have a computational skeleton nobody had priced in.
ปรัชญาโละเรื่องนี้ทิ้งเป็นรายละเอียดทางวิศวกรรมไม่ได้ แถลงการณ์ปี 2011 ของ Scott Aaronson เรื่อง "Why Philosophers Should Care About Computational Complexity" โต้แย้งไว้อย่างนั้น ตรรกศาสตร์เชิงญาณ (epistemic logic) แบบคลาสสิกสมมติผู้กระทำที่เชื่อผลสืบเนื่องเชิงตรรกะทุกข้อของสิ่งที่ตนเชื่อ — ความรอบรู้เชิงตรรกะ (logical omniscience) — และถือว่าข้อสมมตินี้เป็นอุดมคติ แบบที่ฟิสิกส์อุดมคติระนาบไร้แรงเสียดทาน ทฤษฎีความซับซ้อนชี้ว่ามันไม่ใช่อุดมคติ แต่เป็นไปไม่ได้: ความเชื่อธรรมดาจำนวนมาก ถ้าจะอนุมานผลสืบเนื่องให้ครบทุกข้อ ต้องใช้เวลานานเกินอายุเอกภพ ต่อให้ยกคอมพิวเตอร์ทุกเครื่องที่มนุษยชาติสร้างได้มาให้หมดก็ตาม Aaronson ส่องเลนส์เดียวกันนี้ไปที่ปัญหาการอุปนัยของ Hume ปัญหาของ Newcomb และเหตุผลเชิงเศรษฐศาสตร์ — ทุกกรณี ปริศนาที่ดูเป็นเรื่องมโนทัศน์ล้วนๆ กลับมีโครงเชิงคำนวณซ่อนอยู่ข้างในที่ไม่มีใครเคยตีราคาไว้
The clearest case of that skeleton is what P vs NP says about creativity. Checking a completed Sudoku, or a proposed mathematical proof, takes a fixed, modest amount of work regardless of how the answer was found; searching the space of all possible arrangements or all possible proofs is — if P ≠ NP — exponentially harder in the worst case, no matter how cleverly the search is organized. A mathematician's flash of insight, the moment a proof strategy presents itself, may be doing something no systematic algorithm can replace: recognizing is cheap, finding is not, and the distance between them is precisely what complexity theory measures. Chess supplies an older, purer instance of the same gap. Ernst Zermelo proved in 1913 that chess is determined — one of "White forces a win," "Black forces a win," or "both force at worst a draw" is simply true, since the game tree is finite. Nobody knows which, because "finite" and "searchable" are different claims; the game tree is too large for exhaustive analysis by any device anyone expects to build. "Solved in principle" and "true" turn out to be much further apart than either word suggests.
โครงนั้นเห็นชัดที่สุดในสิ่งที่ P vs NP บอกเกี่ยวกับความคิดสร้างสรรค์ การตรวจซูโดกุที่เติมเสร็จแล้ว หรือบทพิสูจน์ทางคณิตศาสตร์ที่เสนอมา ใช้แรงงานเท่าเดิมและไม่มาก ไม่ว่าคำตอบนั้นจะได้มาอย่างไร แต่การไล่ค้นปริภูมิของการจัดเรียงที่เป็นไปได้ทั้งหมด หรือบทพิสูจน์ที่เป็นไปได้ทั้งหมด — ถ้า P ≠ NP — ยากขึ้นแบบยกกำลัง (exponentially) ในกรณีเลวร้ายที่สุด จัดระเบียบการค้นให้ฉลาดแค่ไหนก็ไม่ช่วย ประกายความเข้าใจของนักคณิตศาสตร์ วินาทีที่กลยุทธ์การพิสูจน์ผุดขึ้นมาเอง อาจกำลังทำสิ่งที่ไม่มีอัลกอริทึมเชิงระบบใดแทนได้: จำได้ว่าถูกนั้นถูก หามันเจอนั้นแพง และระยะห่างระหว่างสองอย่างนี้คือสิ่งที่ทฤษฎีความซับซ้อนวัดพอดี หมากรุกให้ตัวอย่างที่เก่ากว่าและบริสุทธิ์กว่าของช่องว่างเดียวกัน Ernst Zermelo พิสูจน์ในปี 1913 ว่าหมากรุก*ถูกกำหนดผลไว้แล้ว* (determined) — หนึ่งในสามข้อ "ขาวบังคับให้ชนะได้" "ดำบังคับให้ชนะได้" หรือ "ทั้งสองฝ่ายบังคับได้อย่างน้อยที่สุดคือเสมอ" เป็นจริงแน่นอน เพราะต้นไม้เกม (game tree) ของมันจำกัด ไม่มีใครรู้ว่าข้อไหน เพราะ "จำกัด" กับ "ค้นหาได้ทั่วถึง" เป็นข้อกล่าวอ้างคนละเรื่อง ต้นไม้เกมใหญ่เกินกว่าอุปกรณ์ใดๆ ที่ใครคาดหวังว่าจะสร้างขึ้นได้จะวิเคราะห์ครบทุกกรณี "แก้ได้ในหลักการ" กับ "จริง" ห่างกันมากกว่าที่คำสองคำนั้นบอกเป็นนัย
Herbert Simon anticipated the gap from the other direction, decades before complexity theory could measure it. His Administrative Behavior (1947) and "A Behavioral Model of Rational Choice" (Quarterly Journal of Economics 69, 1955: 99–118) replaced the classical agent — who surveys every option and every consequence before choosing the best — with a satisficer, who stops at the first option clearing a "good enough" threshold. Simon meant this as psychology, a description of how managers and shoppers actually decide; complexity theory later gave it a floor that is not psychological at all. Any agent operating under a real time budget — human, corporation, or algorithm — is a bounded-rational agent as a matter of physical necessity, whether or not it wants to be.
Herbert Simon เห็นช่องว่างนี้จากอีกด้าน หลายทศวรรษก่อนทฤษฎีความซับซ้อนจะวัดมันได้ หนังสือ Administrative Behavior (1947) และบทความ "A Behavioral Model of Rational Choice" (Quarterly Journal of Economics 69, 1955: 99–118) ของเขาถอดผู้กระทำแบบคลาสสิก — ผู้สำรวจตัวเลือกและผลลัพธ์ทุกข้อก่อนเลือกตัวที่ดีที่สุด — ออก แล้วใส่ผู้กระทำแบบ satisficing (การพอใจแค่พอ) เข้าไปแทน คนที่หยุดตรงตัวเลือกแรกที่ผ่านเกณฑ์ "ดีพอ" Simon ตั้งใจให้นี่เป็นจิตวิทยา เป็นคำอธิบายว่าผู้จัดการและคนซื้อของตัดสินใจกันจริงๆ อย่างไร ทฤษฎีความซับซ้อนมาทีหลังและวางพื้นให้มันใหม่ พื้นที่ไม่เกี่ยวกับจิตวิทยาเลย ผู้กระทำใดก็ตามที่ทำงานใต้งบเวลาจริง — มนุษย์ บริษัท หรืออัลกอริทึม — เป็นผู้กระทำที่มีเหตุผลมีขอบเขต (bounded rationality) โดยความจำเป็นทางกายภาพ อยากเป็นหรือไม่อยากก็ตาม
The same fault line, treated as a resource rather than an obstacle, built modern cryptography. Whitfield Diffie and Martin Hellman's "New Directions in Cryptography" (IEEE Transactions on Information Theory 22, 1976: 644–654) proposed that a "trapdoor one-way function" — easy to compute forward, computationally infeasible to invert without a secret key — could let two strangers agree on a shared secret over an open channel, though the paper offered no working example. RSA supplied one soon after: multiplying two three-hundred-digit primes takes a processor milliseconds; factoring the product back into its primes is believed, by every known method, to take longer than the universe has existed. Every padlock icon in a browser rests not on a proof but on an unproven complexity conjecture — one-way functions are, quite literally, the applied physics of keeping a secret.
รอยแยกเดียวกันนั้น เมื่อถูกใช้เป็นทรัพยากรแทนที่จะเป็นอุปสรรค สร้างวิทยาการเข้ารหัสสมัยใหม่ขึ้นมา บทความ "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) คือฟิสิกส์ประยุกต์ของการเก็บความลับ ตามความหมายตรงตัวเป๊ะๆ
Complexity theory's strangest offspring reworks what a proof even is. Shafi Goldwasser, Silvio Micali, and Charles Rackoff's "The Knowledge Complexity of Interactive Proof-Systems" (17th ACM Symposium on Theory of Computing, Providence, 1985; full version, SIAM Journal on Computing 18, 1989: 186–208) showed that a prover can convince a verifier a statement is true — "these two graphs are isomorphic," "I know the password" — through an interactive back-and-forth whose transcript, read afterward by anyone who wasn't part of the exchange, proves nothing at all. The evidential force lives entirely in the live interrogation and its shrinking probability of letting a cheat through, not in a static object anyone can inspect later. That breaks with every proof from Euclid onward, where a proof is a fixed thing you hand someone and they check alone; here philosophy has grounds to object that computation has redefined "proof" to mean something merely statistical, and complexity theory's honest answer is that the older picture of certainty was never available at scale in the first place — chapter 12 finishes that argument.
ลูกที่แปลกที่สุดของทฤษฎีความซับซ้อนรื้อนิยามของคำว่า "บทพิสูจน์" ใหม่ทั้งอัน บทความ "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 จะปิดข้อโต้แย้งนี้ให้จบ
Whether "possible in principle but not in practice" earns the name metaphysical depends on whether the boundary is fixed or merely historical. Worst-case complexity classes are mathematical facts, but real instances are not always worst cases: practical SAT solvers now settle satisfiability questions with millions of variables that theory calls intractable, because most real formulas are far from the adversarial examples the proofs are built on. The gap between "P ≠ NP" and "this particular problem, today, on this hardware, is out of reach" is where sociology and engineering quietly do the work that pure complexity theory cannot yet certify.
"เป็นไปได้ในหลักการแต่ไม่เป็นไปได้ในทางปฏิบัติ" จะสมควรได้ชื่อว่าเชิงอภิปรัชญาหรือไม่ ขึ้นอยู่กับว่าเส้นขอบนั้นตายตัว หรือเป็นแค่เรื่องเชิงประวัติศาสตร์ คลาสความซับซ้อน (complexity class) แบบกรณีเลวร้ายที่สุดเป็นข้อเท็จจริงทางคณิตศาสตร์ แต่ตัวอย่างจริงไม่ได้เป็นกรณีเลวร้ายที่สุดเสมอไป: ตัวแก้ SAT เชิงปฏิบัติทุกวันนี้ปิดคำถาม satisfiability ที่มีตัวแปรเป็นล้านตัวได้ ทั้งที่ทฤษฎีเรียกมันว่าแก้ไม่ได้ในทางปฏิบัติ (intractable) เพราะสูตรจริงส่วนใหญ่อยู่ไกลจากตัวอย่างปฏิปักษ์ (adversarial examples) ที่บทพิสูจน์เหล่านั้นสร้างขึ้นบนฐานของมัน ช่องว่างระหว่าง "P ≠ NP" กับ "ปัญหาข้อนี้โดยเฉพาะ วันนี้ บนฮาร์ดแวร์นี้ อยู่นอกเอื้อม" คือจุดที่สังคมวิทยาและวิศวกรรมทำงานเงียบๆ แทนสิ่งที่ทฤษฎีความซับซ้อนล้วนๆ ยังรับรองไม่ได้
Connections
เชื่อมโยง
Chapter 09 established what computation can do at all; this chapter measures what it can do inside a clock. Chapter 03 asked whether machine testimony counts as knowledge; interactive proof is that question with a probability attached. Chapter 06 meets the same impossibility-result shape in algorithmic fairness. Chapter 11 takes up Kolmogorov complexity, the cousin of computational complexity that measures description length rather than running time.
บทที่ 09 วางไว้ว่าการคำนวณทำอะไรได้บ้างในหลักการ บทนี้วัดว่ามันทำอะไรได้ภายในเวลาที่มีจำกัด บทที่ 03 ถามว่าคำให้การของเครื่องจักรนับเป็นความรู้หรือไม่ interactive proof คือคำถามข้อนั้นที่ติดความน่าจะเป็นมาด้วย บทที่ 06 เจอรูปแบบผลลัพธ์ความเป็นไปไม่ได้แบบเดียวกันในความเป็นธรรมเชิงอัลกอริทึม (algorithmic fairness) บทที่ 11 รับช่วงต่อด้วย Kolmogorov complexity ญาติของความซับซ้อนเชิงคำนวณที่วัดความยาวคำอธิบายแทนเวลาในการรัน
Open questions
คำถามที่ยังเปิดอยู่
If P vs NP were resolved tomorrow, would it settle a metaphysical question or only a mathematical one? Does the gap between worst-case hardness and real-world tractability mean complexity classes describe the world, or only the adversaries mathematicians have chosen to imagine? And if bounded rationality is a physical necessity for any agent, what is left of the classical picture of a fully rational ideal observer that philosophy built its theories of knowledge and choice around?
ถ้า P vs NP ถูกคลี่คลายพรุ่งนี้ มันยุติคำถามเชิงอภิปรัชญา หรือยุติแค่คำถามเชิงคณิตศาสตร์? ช่องว่างระหว่างความยากแบบกรณีเลวร้ายที่สุดกับความแก้ได้จริงในโลกจริง แปลว่าคลาสความซับซ้อนอธิบายโลก หรืออธิบายแค่ปฏิปักษ์ที่นักคณิตศาสตร์เลือกจะจินตนาการขึ้นมา? และถ้าเหตุผลมีขอบเขต (bounded rationality) เป็นความจำเป็นทางกายภาพของผู้กระทำทุกราย ภาพคลาสสิกของผู้สังเกตการณ์ในอุดมคติที่มีเหตุผลเต็มเปี่ยม ภาพที่ปรัชญาสร้างทฤษฎีความรู้และการเลือกขึ้นมาบนมัน ยังเหลืออะไรอยู่?
Go deeper
อ่านต่อ
- 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.
- 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.