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