
Kristina Armitage/นิตยสาร Quanta
ถ้านักวิทยาศาสตร์คอมพิวเตอร์หลายล้านคนทานอาหารเย็นด้วยกัน พวกเขาจะเก็บเงินมหาศาล และถ้าคนใดคนหนึ่งรู้สึกประหยัดเป็นพิเศษและต้องการตรวจสอบว่าใบเรียกเก็บเงินถูกต้องหรือไม่ กระบวนการก็จะตรงไปตรงมา ถ้าน่าเบื่อ พวกเขาจะต้องผ่านการเรียกเก็บเงินและบวกทุกอย่างทีละบรรทัดเพื่อให้ แน่ใจว่าผลรวมเท่ากับยอดรวมที่ระบุไว้
แต่ในปี 1992 นักวิทยาศาสตร์คอมพิวเตอร์หกคนได้พิสูจน์ในเอกสาร สอง ฉบับ ว่าทางลัดที่ต่างไปจากเดิมอย่างสิ้นเชิงนั้นเป็นไปได้ มีวิธีในการจัดรูปแบบใบเรียกเก็บเงินใหม่ ไม่ว่าจะยาวแค่ไหนก็ตาม เพื่อให้สามารถตรวจสอบได้ด้วยคำถามเพียงไม่กี่ข้อ ที่สำคัญกว่านั้น พวกเขาพบว่าสิ่งนี้เป็นจริงสำหรับการคำนวณใดๆ หรือแม้แต่การพิสูจน์ทางคณิตศาสตร์ใดๆ เนื่องจากทั้งคู่มาพร้อมกับใบเสร็จรับเงิน ดังนั้นเพื่อพูดคือ: บันทึกขั้นตอนที่คอมพิวเตอร์หรือนักคณิตศาสตร์ต้องทำ
รูปแบบที่รัดกุมอย่างน่าทึ่งนี้เรียกว่าการพิสูจน์ที่ตรวจสอบได้เชิงความน่าจะเป็น (PCP) ( ตามคำกล่าวของ Ryan O’Donnell คำย่อนี้เห็นได้ชัดว่าได้รับเลือกหลังจากที่ตำรวจเข้าไปที่ห้องพักในโรงแรมของหนึ่งในนักประดิษฐ์ Shmuel Safra อย่างผิดพลาด ขณะที่พยายามจะสกัดกั้นยาที่เป็นไปได้สำหรับ phenylcyclohexyl piperidine หรือที่เรียกว่า PCP หรือ angel dust .)
PCP ได้กลายเป็นเครื่องมือที่สำคัญที่สุดในวิทยาการคอมพิวเตอร์เชิงทฤษฎี เมื่อเร็ว ๆ นี้ พวกเขายังพบวิธีการในการใช้งานที่ใช้งานได้จริง เช่น ในสกุลเงินดิจิทัล ซึ่งใช้สำหรับรวบรวมธุรกรรมจำนวนมากให้อยู่ในรูปแบบที่เล็กลงซึ่งง่ายต่อการตรวจสอบ
Dan Boneh จากมหาวิทยาลัยสแตนฟอร์ดกล่าวว่า “ฉันไม่รู้ตัวอย่างใด หรืออาจเป็นแค่เครื่องมือที่หายากมากเท่านั้น
ก่อนที่จะมีการสร้าง PCP นักวิทยาศาสตร์คอมพิวเตอร์ได้ระบุปัญหาทั้งกลุ่มด้วยวิธีแก้ปัญหาที่คล้ายกับการตรวจทานอาหารเย็น ซึ่งง่ายต่อการตรวจสอบเมื่อคุณมีแล้ว แต่สำหรับปัญหาเหล่านี้หลายๆ อย่าง การหาทางแก้ไขตั้งแต่แรกดูเหมือนจะใช้เวลามากจนทำไม่ได้
นักวิทยาศาสตร์คอมพิวเตอร์ตั้งชื่อคลาสนี้ว่าปัญหาที่แก้ยากแต่มีประสิทธิภาพในการตรวจสอบยืนยัน NP เป็นบ้านเชิงแนวคิดสำหรับปัญหาเชิงปฏิบัติจำนวนมากที่เราสนใจ และปัญหาที่เป็นนามธรรมอีกมากมาย เช่น การค้นหาข้อพิสูจน์ของทฤษฎีบททางคณิตศาสตร์ การพิสูจน์เป็นสูตรทีละขั้นตอนที่สร้างข้อสรุปทางคณิตศาสตร์ด้วยความแน่นอน – เช่นเดียวกับใบเรียกเก็บเงินแยกรายการให้หลักฐานของยอดค้างชำระ หลักฐานอาจเป็นเรื่องยากที่จะได้รับ แต่เมื่อคุณมีแล้ว จะสามารถตรวจสอบได้อย่างตรงไปตรงมา นั่นทำให้การพิสูจน์ถูกต้องในหมวดหมู่ของ NP
ในช่วงปี 1980 นักวิทยาศาสตร์คอมพิวเตอร์เริ่มจินตนาการใหม่ว่าการพิสูจน์เป็นอย่างไร นักเข้ารหัสสงสัยว่าเป็นไปได้หรือไม่ที่จะรู้ว่าข้อพิสูจน์นั้นเป็นความจริงโดยไม่ได้ดูเนื้อหา พวกเขาแยกโครงสร้างของการพิสูจน์เป็นระบบสองส่วน โดยมี “ผู้ตรวจสอบ” ที่พยายามตรวจสอบหลักฐานซึ่งจัดทำโดย “ผู้พิสูจน์” ซึ่งหาหลักฐานมาได้
ทฤษฎีบท PCP ในปี 1992 แสดงให้เห็นว่าผู้พิสูจน์สามารถเข้ารหัสการพิสูจน์ในรูปแบบใหม่ได้เสมอ เพื่อให้สามารถยืนยันได้ด้วยจำนวนคำถามคงที่ โดยไม่คำนึงถึงความยาวดั้งเดิมของหลักฐาน ในที่สุดจำนวนคำถามที่จำเป็นนั้นก็ลดลงเหลือเพียงสองหรือสามรายการ ผู้ตรวจสอบจะไม่ทราบว่ามันเป็นเรื่องจริงด้วยความแน่นอนอย่างยิ่ง แต่การตั้งคำถามเพิ่มเติมจะทำให้ความแน่นอนเพิ่มขึ้นอย่างต่อเนื่องและตรงไปตรงมา ผลที่ได้ขัดกับสัญชาตญาณ หลักฐานที่ยาวกว่านั้นจะทำให้คุณต้องตรวจสอบหลักฐานเพิ่มเติมหรือไม่? ไม่อย่างนั้น
Swastik Kopparty จากมหาวิทยาลัยโตรอนโตกล่าวว่า “ไม่น่าเชื่อว่าเรื่องดังกล่าวจะเป็นจริง “จนกระทั่งไม่นานก่อนที่ทฤษฎีบท PCP จะได้รับการพิสูจน์ ไม่มีใครกล้าแม้แต่จะพูดออกมาเช่นนี้”
ทฤษฎีบทนี้ให้ความเข้าใจใหม่เกี่ยวกับ NP และอธิบายคุณสมบัติที่น่าสนใจบางประการ นักวิทยาศาสตร์คอมพิวเตอร์พบว่าสำหรับปัญหา NP บางอย่าง คำตอบดูเหมือนจะไม่เพียงแต่คำนวณได้ยาก แต่ยังคาดเดาได้ยากอีกด้วย ทฤษฎีบท PCP ช่วยอธิบายว่าทำไม มันบอกว่าหากพบวิธีแก้ไขปัญหา NP ก็สามารถจัดรูปแบบใหม่ได้ตลอดเวลาในลักษณะที่การตรวจสอบส่วนใหญ่จากผู้ตรวจสอบ (กล่าว 90 เปอร์เซ็นต์) จะผ่าน (แต่ไม่ใช่ทั้งหมดเพราะการพิสูจน์ยังเป็นเพียงความน่าจะเป็น) จากจุดได้เปรียบของผู้ตรวจสอบจึงดูเหมือนว่าปัญหาได้รับการแก้ไขแล้วประมาณร้อยละ 90 จนถึงความถูกต้อง แต่เนื่องจากปัญหา NP แก้ได้ยาก จึงมักเป็นเรื่องยากที่จะหา PCP สำหรับปัญหาเหล่านี้ ดังนั้นจึงยากพอๆ กันที่จะหาวิธีแก้ไขที่ถูกต้องเกินจุดหนึ่งโดยประมาณ (เช่น 90 เปอร์เซ็นต์)
นักวิทยาศาสตร์ก็เริ่มคิดเกี่ยวกับความเป็นไปได้ของการใช้งานจริงสำหรับ PCP น่าเสียดายที่ PCP ในยุค 90 นั้นไม่มีประสิทธิภาพอย่างไม่มีการลด ต้องใช้เวลาหลายพันปีกว่าที่ผู้พิสูจน์จะผลิต PCP ที่แสดงถึงการคำนวณในทางปฏิบัติใดๆ นอกจากนี้ PCP จริง ๆ จะต้องมีขนาดใหญ่มาก ซึ่งต้องใช้ฮาร์ดไดรฟ์ขนาดเท่าดาวเคราะห์
แต่ในปี 2551 นักวิจัยพบว่า PCP มีขนาดและการคำนวณที่ขยายช้ากว่ามาก ทำให้จัดการได้ง่ายขึ้น จากนั้นในช่วงกลางปี 2010 นักวิจัยเริ่มสร้าง PCP รูปแบบใหม่ที่มีขนาดเล็กกว่านั้น เรียกว่า Interactive oracle proofs (IOPs) ซึ่งเพิ่มรอบเพิ่มเติมของการมีปฏิสัมพันธ์ระหว่างผู้ตรวจสอบและผู้ตรวจสอบ โดยในแต่ละรอบ ผู้ตรวจสอบสามารถสร้างบางสิ่งได้ เล็กกว่ามากเร็วกว่ามาก
Eli Ben-Sasson นักวิทยาศาสตร์คอมพิวเตอร์ที่ออกจาก Technion ในเมืองไฮฟา ประเทศอิสราเอล กล่าวว่า “การเพิ่มปฏิสัมพันธ์และการใช้คณิตศาสตร์แบบเดียวกับที่ถ่ายทอดจากเทคโนโลยี PCP ทำให้คุณได้สิ่งที่ใช้ได้จริง” Eli Ben-Sasson นักวิทยาศาสตร์คอมพิวเตอร์ที่ออกจาก Technion ในไฮฟา ประเทศอิสราเอล เพื่อก่อตั้งบริษัท StarkWare กล่าว
ในทศวรรษที่ผ่านมา นักวิทยาศาสตร์คอมพิวเตอร์ยังพบแอปพลิเคชันโดยตรงสำหรับ PCP (และลูกหลานของพวกมัน) ในซอฟต์แวร์ที่อยู่เบื้องหลัง cryptocurrencies ซึ่งขณะนี้กำลังทำให้เกิดคำถามเชิงทฤษฎีที่น่าสนใจสำหรับพวกเขาเอง ในระบบซอฟต์แวร์ระบบใดระบบหนึ่งเหล่านี้ คอมพิวเตอร์ขนาดใหญ่ (ผู้ตรวจสอบ) จะตรวจสอบความถูกต้องของธุรกรรมทางการเงิน และวางการคำนวณการตรวจสอบความถูกต้องลงใน PCP เพื่อให้คอมพิวเตอร์ขนาดเล็ก (ผู้ตรวจสอบ) สามารถตรวจสอบความถูกต้องของธุรกรรมได้เร็วกว่ามาก
แต่สมมุติว่าผู้พิสูจน์พยายามโกง ตัวอย่างเช่น โดยการปกปิดชุดของธุรกรรมที่เป็นเท็จภายใน PCP เมื่อระบบ PCP (ประกอบด้วยเครื่องพิสูจน์ ผู้ตรวจสอบ และ PCP) สามารถต้านทานการหลอกลวงประเภทนี้ได้ นักวิจัยกล่าวว่าระบบมี “ความถูกต้อง” ความสมบูรณ์เป็นสิ่งสำคัญทั้งในทางทฤษฎีและในการใช้งานจริง โดยที่ความสมบูรณ์ที่ดีขึ้น (วัดด้วยพารามิเตอร์บางอย่าง) แปลเป็นการตรวจสอบที่เร็วขึ้นและงานคำนวณน้อยลง
บทความที่ เผยแพร่ในเดือนพฤษภาคม 2020 โดย Ben-Sasson, Dan Carmon, Yuval Ishai, Kopparty และ Shubhangi Saraf แสดงให้เห็นว่าความสมบูรณ์ของระบบ PCP สมัยใหม่หนึ่งระบบถึงขีดจำกัดพื้นฐานจากวิทยาการคอมพิวเตอร์เชิงทฤษฎี นี่คือความทนทานสูงสุดของข้อมูลที่ทราบเมื่อมีการเข้ารหัสในรูปแบบคลาสสิกที่เรียกว่าการเข้ารหัสรีดโซโลมอน ซึ่งเป็นวิธีเข้ารหัสการพิสูจน์หรือการคำนวณโดย PCP
PCP ยังสามารถทำให้มีประสิทธิภาพมากขึ้น เมื่อเร็ว ๆ นี้ นักวิจัยสองกลุ่มได้ ค้นพบ วิธีที่ เหมาะสมที่สุด ในการเข้ารหัสกลุ่มข้อมูลขนาดใหญ่ โดยการตรวจสอบเพียงไม่กี่จุดจะเผยให้เห็นว่าบล็อกทั้งหมดเสียหายหรือไม่ วิธีนี้ทำบางสิ่งที่คล้ายกับ PCP โดยให้การทดสอบความสมบูรณ์ซึ่งขึ้นอยู่กับการสืบค้นเพียงไม่กี่ครั้ง ในขณะที่ยังบรรลุประสิทธิภาพที่สมบูรณ์แบบในแง่ของความเร็วและขนาด นักวิจัยมองว่าเป็นข้อพิสูจน์ว่าวันหนึ่งอาจพบ PCP ที่เหมาะสมที่สุดได้
“มันไม่ใช่ปัญหาง่าย” Dana Moshkovitz จากมหาวิทยาลัยเท็กซัส ออสตินกล่าว “[แต่] รู้สึกว่าเราควรไปและทำมัน”