13 · ตรวจจนจักรวาลดับ
สมมติว่าคุณได้รับข้อความสองข้อความในเช้าเดียวกัน ข้อความแรกว่า รหัสเปิดตู้เซฟใบนี้คือเลขชุดนี้ ข้อความที่สองว่า ในตราสารหนี้หนึ่งพันกองที่คุณกำลังจะซื้อ ไม่มีกองไหนถูกวางกับดักไว้ ข้อความแรกคุณกดเลขครั้งเดียวก็รู้ผล ข้อความที่สองคุณจะตรวจเสร็จเมื่อไร
ข้ออ้างที่ตรวจไม่ทันจนจักรวาลดับมักมีหน้าตาเดียวกัน คืออ้างว่าไม่มี ข้ออ้างว่ามีพกพยานมาด้วย เลขชุดหนึ่ง เส้นทางหนึ่ง รายชื่อหนึ่ง ตรวจพยานแล้วจบ ข้ออ้างว่าไม่มีส่วนมากไม่มีพยานสั้น ๆ ให้ยื่น บางข้อมีทางลัด เช่น ตาราง Sudoku ตารางเดียวมีเลขซ้ำในแถวไหนไหม ไล่ดูไม่กี่วินาทีก็ครบ เพราะที่ที่ต้องดูมีน้อย ข้ออ้างว่าไม่มีจะแพงจริงเมื่อที่ที่ต้องดูมีมากจนไล่ไม่หมด และไม่มีใครรู้ทางลัด จะตรวจมัน คุณต้องไล่ดูทุกที่ที่สิ่งนั้นอาจซ่อนอยู่ และบางครั้งทุกที่ก็มีมากกว่าที่จักรวาลจะไล่ทัน
ตรวจง่าย หายาก
สถาบันคณิตศาสตร์ Clay ตั้งรางวัลหนึ่งล้านดอลลาร์ให้ปัญหาชื่อ P vs NP ไว้ตั้งแต่ปี 2000 และอธิบายมันด้วยหอพัก ต้องเลือกนักศึกษา 100 คนจากผู้สมัคร 400 คน โดยมีรายชื่อคู่ที่ห้ามอยู่ด้วยกัน รายชื่อที่มีคนยื่นมา คุณไล่เทียบทีละคู่ก็ตรวจเสร็จ แต่ถ้าต้องหาเอง "จำนวนวิธีเลือกนักศึกษาหนึ่งร้อยคนจากผู้สมัครสี่ร้อยคน มากกว่าจำนวนอะตอมในจักรวาลที่รู้จัก"
Stephen Cook กับ Leonid Levin ตั้งคำถามนี้แยกกันในปี 1971 P คือปัญหาที่หาคำตอบได้ง่าย NP คือปัญหาที่ตรวจคำตอบได้ง่าย สองกลุ่มนี้คือกลุ่มเดียวกันหรือไม่ หน้าเว็บของ Clay ในปี 2026 ยังติดป้ายว่า Unsolved
เมื่อคนปลอมต้องเป็นฝ่ายค้น
ถ้าคนที่ต้องหาคือคนปลอม ช่องว่างนี้คือกำแพงของทีมตรวจ กุญแจเข้ารหัสยาว 128 bit มีค่าที่เป็นไปได้ราว 3.4 × 10³⁸ ดอก คนปลอมต้องไล่ลองทีละดอก ต่อให้ลองได้วินาทีละ 10¹⁸ ดอก การไล่ให้ครบก็กินเวลาราว 1.08 × 10¹³ ปี เท่ากับราว ราว 780 เท่าของอายุจักรวาล ที่ภารกิจ Planck ประเมินไว้ราว 13,800 ล้านปีในปี 2018 ตัวเลขนี้เล่มนี้คำนวณเอง กำแพงแบบนี้ยืนได้เท่าที่ยังไม่มีใครหาทางลัดเจอ เครื่อง bombe ที่ Bletchley Park พัง Enigma ได้ ก็เพราะ crib ข้อความที่เดาไว้ล่วงหน้า คือทางลัด
ข้ออ้างที่ไม่มีพยาน
ทีนี้กลับด้าน ให้คนปลอมเป็นฝ่ายซ่อน ในปี 2010 Sanjeev Arora, Boaz Barak, Markus Brunnermeier และ Rong Ge สร้างแบบจำลองธนาคารที่มัดสินเชื่อบ้านเป็น CDO หลายพันกอง บางกลุ่มเป็นของเสียที่ผิดนัดแน่นอน ธนาคารแอบยัดของเสียลงในบางกองที่เลือกไว้ได้ กับดักนี้ปรากฏเป็นกลุ่มที่โยงกันแน่นผิดปกติ การหามันคือปัญหา planted dense subgraph นึกภาพจุดสองแถว แถวหนึ่งคือกลุ่มสินเชื่อ อีกแถวคือกอง CDO แล้วลากเส้นจากสินเชื่อไปยังกองที่มันถูกใส่ กองที่ถูกวางกับดักจะโยงกับกลุ่มของเสียเป็นก้อนเส้นที่แน่นกว่าที่ควร การหาก้อนแน่นแบบนั้นในกองเส้นมหาศาล คือปัญหาที่เชื่อกันว่ายาก ผู้ซื้อที่มีเวลาคำนวณจำกัดจับไม่ได้ ในแบบจำลองนี้
ผู้เขียนยังบอกว่า "เชื่อกันว่าไม่มีวิธีง่าย ๆ ที่จะพิสูจน์ว่ากลุ่มที่แน่นแบบนี้ไม่มีอยู่" ธนาคารที่ซื่อจึงน่าจะพิสูจน์ความซื่อของตัวเองไม่ได้ ตามข้อสันนิษฐานนั้น และหลังขาดทุนแล้ว ผู้ซื้อก็ "จะพิสูจน์ไม่ได้ว่าความเสียหายมาจากการแทรกแซงของผู้ขาย" แต่นี่คือทฤษฎีบทในแบบจำลองที่ผู้เขียนเองบอกว่า "ทำให้ง่ายลงมาก" ตั้งอยู่บนข้อสันนิษฐาน ไม่ได้ชี้ว่าธนาคารไหนทำจริง และในแบบจำลองนั้นมีวิธีออกแบบตราสารที่วางกับดักไม่ได้ ทางออกจึงเหมือนซองดินที่ซูซา คือทำของให้ตรวจได้ตั้งแต่ตอนสร้าง
คำว่า ไม่มีทางไหนถูกกว่านี้แล้ว ก็หน้าตาเดียวกัน เส้นทางวนผ่าน 30 เมืองวัดความยาวได้ง่าย แต่จะยืนยันว่าไม่มีเส้นไหนสั้นกว่าด้วยการไล่นับ ต้องเทียบราว 4.42 × 10³⁰ เส้น ตัวเลขนี้เล่มนี้คำนวณเอง เป็นภาพประกอบ ไม่ใช่ทฤษฎีบทว่าตรวจเร็วกว่านี้ไม่ได้ (สำหรับเมืองจำนวนเท่านี้ นักคณิตศาสตร์มีเทคนิคที่พิสูจน์ได้ว่าไม่มีเส้นทางสั้นกว่า โดยไม่ต้องลองทุกเส้น แต่ยังไม่มีใครรู้วิธีที่ใช้ได้รวดเร็วกับทุกกรณี)
ประตูที่ปิดแล้ว
ข้ออ้างอีกชุดหนึ่งไม่ได้รอทางลัด ประตูของมันปิดไปแล้ว ในปี 1936 Alan Turing พิสูจน์ว่ามีคำถามเกี่ยวกับเครื่องคำนวณที่ไม่มีเครื่องใดตอบถูกได้กับทุกเครื่อง รูปที่รู้จักกันดีได้ชื่อในภายหลังว่า halting problem ในปี 1953 H. G. Rice ขยายมันเป็น Rice's theorem คำถามเกี่ยวกับ พฤติกรรม ของโปรแกรมที่ไม่ได้ตอบเหมือนกันทุกโปรแกรม ไม่มีขั้นตอนวิธีเดียวที่ตอบถูกกับทุกโปรแกรม คำว่า โปรแกรมนี้ไม่มีวันส่งข้อมูลของคุณออกไป จึงไม่มีเครื่องตรวจทั่วไปรับรองได้ แม้โปรแกรมทีละตัวยังพิสูจน์ได้
ในปี 1974 Chaitin ปิดอีกบาน ระบบที่มีสัจพจน์ขนาด N bit พิสูจน์ไม่ได้ว่าสายตัวเลขใดมี Kolmogorov complexity สูง (ความยาวของคำอธิบายที่สั้นที่สุดที่สร้างสายตัวเลขนั้นได้)เกิน N บวกค่าคงที่ไปมาก คำว่า ตัวเลขชุดนี้สุ่มจริง จึงรับรองได้ไม่เกินข้อมูลที่ใส่ไว้ในสัจพจน์
เล่มนี้เรียกแบบที่ห้าของการตรวจไม่ทันว่า ตรวจไม่ได้ ชื่อนี้เป็นของเล่มนี้เองเหมือนอีกสี่แบบ สี่แบบแรกแก้ได้ด้วยของที่หาได้ในโลก จะเป็นเงิน เวลา คนที่ยอมเสียห้านาที ช่องทางที่คนปลอมไม่ได้แตะ หรือข้อสอบชุดใหม่ แต่ตรวจไม่ได้คือกรณีที่ไม่มีการตรวจจำนวนขั้นจำกัดใดจบได้ หรือเท่าที่มนุษย์รู้ในวันนี้ไม่มีวิธีไหนทำทันในโลกจริง
แบบนี้ล้มได้ ถ้ามีคนพิสูจน์ว่า P = NP พร้อมวิธีที่ใช้ได้จริง กับดักใน CDO จะตรวจทัน แต่คนปลอมก็จะค้นได้ถูกลง และกำแพง 782 เท่าของอายุจักรวาลจะพังไปด้วย ส่วนประตูของ Turing, Rice และ Chaitin ไม่ขึ้นกับคำตอบนั้นเลย
กาน้ำชาระหว่างโลกกับดาวอังคาร
ข้ออ้างว่ามีบางข้อก็หักล้างไม่ได้ด้วยเหตุผลเดียวกัน เพราะการหักล้างมันคือการพิสูจน์ว่าไม่มี
ต้นปี 1952 นิตยสาร Illustrated ขอบทความจาก Bertrand Russell ต้นฉบับ Is There a God? ถูกชมว่า "น่าสนใจที่สุดและอ่านง่ายอย่างยิ่ง" แล้วไม่ได้ลงพิมพ์ตลอดชีวิตของเขา ผู้รวบรวมงานของ Russell บันทึกว่าเหตุผล "ยังเป็นปริศนา" บทความว่าด้วยข้ออ้างที่พิสูจน์ไม่ได้ จึงได้ปริศนาแถมมาอีกหนึ่ง
ในบทความนั้น Russell เขียนว่า "ถ้าข้าพเจ้าจะเสนอว่า ระหว่างโลกกับดาวอังคารมีกาน้ำชากระเบื้องใบหนึ่งโคจรรอบดวงอาทิตย์เป็นวงรี ก็จะไม่มีใครหักล้างข้ออ้างของข้าพเจ้าได้ หากข้าพเจ้าระวังเติมไว้ด้วยว่ากาน้ำชาใบนั้นเล็กเกินกว่ากล้องโทรทรรศน์ที่ทรงพลังที่สุดของเราจะมองเห็น แต่ถ้าข้าพเจ้าพูดต่อไปว่า เพราะข้ออ้างของข้าพเจ้าหักล้างไม่ได้ การที่เหตุผลของมนุษย์จะสงสัยมันจึงเป็นความอวดดีที่ทนไม่ได้ ข้าพเจ้าก็สมควรถูกมองว่ากำลังพูดเรื่องไร้สาระ"
Russell ไม่ได้บอกว่ากาน้ำชาไม่มี เขาบอกว่าภาระย้ายข้าง และข้ออ้างแบบนี้ก็คือแบบตรวจไม่ได้ คำถามจึงไม่ใช่จะตรวจให้เร็วขึ้นอย่างไร แต่คือใครถือภาระ คนขายที่บอกว่าไม่มีกับดัก คนเขียนสัญญาที่บอกว่าไม่มีค่าธรรมเนียมแอบแฝง คนที่บอกว่ามีกาน้ำชาลอยอยู่ในอวกาศ ถ้าเขายื่นหลักฐานไม่ได้ คุณวางข้ออ้างนั้นลงได้เลย
บทถัดไป · 15 / 2014 The Proofช่วงพากย์ · นัดที่ 13 · ระหว่างโลกกับดาวอังคาร ปี 1952
น้าไว: ทีมปลอมยื่นใบรับรองครับ เขียนตัวโตว่า ไม่มีกับดัก อาจารย์จะขอดูรีเพลย์ทุกมุมเลยไหมครับ
อาจารย์ช้า: ทุกมุมของเรื่องนี้ต้องรอจักรวาลดับครับน้า ครั้งนี้อาจารย์ไม่รอ ใครอ้างอะไร คนนั้นแบกหลักฐานเองครับ
น้าไว: แล้วกาน้ำชาที่กล้องส่องไม่เห็นล่ะครับ
อาจารย์ช้า: เชิญเจ้าของส่องให้เห็นเองครับ
สกอร์บอร์ด
อายุของปลอม: ข้ออ้างว่าไม่มี รอดได้ไม่มีกำหนด
การตรวจที่จับได้ใช้เวลา: ไม่มีวันจบ ถ้าต้องไล่ดูทุกที่
แบบของการตรวจไม่ทัน: ตรวจไม่ได้