ฉันจะพยายามตอบสิ่งที่ฉันเชื่อว่าเป็นสิ่งที่คุณถามคือ:
ถ้า $P = NP$สามารถ "แก้ไข" การเข้ารหัสได้โดยการแทนที่สิ่งก่อสร้างด้วย เชิงโต้ตอบ โปรโตคอล?
นี่เป็นคำถามที่เป็นธรรมชาติ แต่มีคำตอบที่เป็นที่รู้จักกันดี (เชิงลบ)
โดยเฉพาะอย่างยิ่ง โปรโตคอลแบบโต้ตอบใด ๆ ที่ต้องการจำนวนรอบการโต้ตอบที่แน่นอน (จำกัด) กล่าวกันว่าอยู่ในคลาสความซับซ้อนที่เรียกว่า ลำดับชั้นพหุนาม $PH$. มันคือ เบื้องต้น เป็นไปได้ว่า $P = NP$, แต่ $P \subsetneq PH$.
ในการตั้งค่านี้ คำตอบสำหรับคำถามข้างต้นคือ "ใช่ โดยหลักการแล้ว" (แม้ว่าฉันจะรู้ว่าไม่มีโครงสร้างก็ตาม)
น่าเสียดายที่หนึ่งในผลลัพธ์พื้นฐานเกี่ยวกับ $PH$ คือว่านี้เป็นเท็จ ความหมาย $P = NP\หมายถึง P=PH$ดังนั้นจึงใช้การเข้ารหัส (ในโลกที่ $P = NP$) ไม่สามารถโต้ตอบได้ในจำนวนจำกัด
มีข้อแม้บางประการเกี่ยวกับโปรโตคอลที่มี $\โอเมก้า(1)$ รอบ (สิ่งเหล่านี้อยู่ในคลาสความซับซ้อนที่เรียกว่า ไอพี) แต่สิ่งเหล่านี้จะช้าอย่างไม่น่าเชื่อ (เนื่องจากแต่ละรอบมีความหน่วงแฝงที่หลีกเลี่ยงไม่ได้จากความเร็วแสง) ซึ่งไม่น่าสนใจเป็นพิเศษ
มีอีกสองสามวิธีที่เป็นไปได้ในการรับ (เช่น) การเข้ารหัสในโลกที่ $P = NP$ แม้ว่ากล่าวคือ:
- โดยใช้สมมติฐาน "noisy channel" เช่น ช่องดักฟัง, และ
- การใช้ช่องควอนตัม
ทั้งสองมีข้อเสียที่สำคัญเมื่อเทียบกับการเข้ารหัสตามทฤษฎีความซับซ้อน (ซึ่งฉันจะไม่พยายามสรุปที่นี่) แต่ความถูกต้องไม่ได้ถูกคุกคามโดย $P = NP$และอาจเป็นสิ่งที่ดีในการค้นหาหากคุณสนใจในความเป็นไปได้ของการสื่อสารที่ปลอดภัยในโลกที่ $P = NP$.
ที่กล่าวมาทั้งหมด การยืนยันตัวตนของคุณกับคอมพิวเตอร์โดยรวมจะยากกว่ามาก
"วิธีแก้ปัญหา" อีกประการหนึ่งคือการใช้การรับรองความถูกต้องด้วยตนเอง
แน่นอนว่าเราสามารถประพฤติตัวฉ้อฉลได้ที่นี่ แต่มันค่อนข้างยากกว่าที่จะทำในระดับหนึ่ง