P = NP ใน Cellular Automata ของ Hyperbolic Spaces หรือไม่

Aug 18 2020

ผมอ่านไม่กี่ปีที่ผ่านมาในหนังสือเล่มนี้ว่าปัญหา NP เป็นเวไนยในพื้นที่ของเซลล์ออโตมาในระนาบการผ่อนชำระ สิ่งนี้หมายความว่า? ไม่P = NPเป็นไปตามหนังสือเหล่านี้ / เอกสาร?

ข้อความที่ตัดตอนมาจากกระดาษ:

เป็นที่ทราบกันดีอยู่แล้วว่าหากเรามีต้นไม้ไบนารีให้ใช้งานได้“ ฟรี” มันเป็นไปได้ที่จะแก้ปัญหา NP ในรูปแบบพหุนามดู [14, 5] อย่างไรก็ตามไม่สามารถใช้อัลกอริทึมต้นไม้ไบนารีในรูปห้าเหลี่ยมในทันทีและเป้าหมายของส่วนนี้คือการระบุว่าจะดำเนินการอย่างไร

จากความเข้าใจของฉันปัญหาP = NPกำลังมองหาอัลกอริธึมเวลาพหุนามเพื่อแก้ปัญหาที่ซับซ้อน จากการมองคร่าวๆของฉันผ่านหนังสือและเอกสารดูเหมือนว่าเขาจะแก้ปัญหาได้แล้ว ฉันขาดอะไรไป?

นี่คือกระดาษอีกบรรดาศักดิ์ในบางโค้ง Spaces เราสามารถแก้ NP-ฮาร์ดปัญหาในการพหุนามเวลา: ต่อ Matiyasevich ฝัน

คำตอบ

7 Discretelizard Aug 18 2020 at 15:22

ปัญหา P เทียบกับ NP เป็นคำถามเกี่ยวกับเครื่องจักรทัวริง $T$เนื่องจากคลาสความซับซ้อน P และ NP ถูกกำหนดไว้ในรูปแบบของเครื่องจักรทางทฤษฎีเหล่านี้ เรียกคลาสเหล่านี้ว่า$P_T$ และ $NP_T$จากนี้ไป. บทความนี้แนะนำเครื่องคำนวณทางทฤษฎีใหม่$H$ ที่มีคลาสที่เกี่ยวข้อง $P_H$ (ทำงานในเวลาพหุนามบน hyperbolic cellular automaton) และ $NP_H$ (ทำงานในเวลาพหุนามที่ไม่ได้กำหนดบน hyperbolic cellular automaton)

ขั้นตอนแรกในบทความนี้เป็นการพิสูจน์ว่าปัญหา 3SAT ซึ่งเป็นที่รู้จักกันดี $NP_T$- ปัญหาที่สมบูรณ์สามารถแก้ไขได้ในเวลาพหุนามบนเครื่องนี้กล่าวคือปัญหานี้อยู่ใน $P_H$. จากนั้นจะแสดงการลดเวลาพหุนามบนเครื่องทัวริงที่สามารถทำได้ในรูปแบบพหุนามบนหุ่นยนต์ไฮเปอร์โบลิก ตั้งแต่ 3SAT คือ$NP_T$- สมบูรณ์ใด ๆ $NP_T$ สามารถลดอินสแตนซ์เป็นอินสแตนซ์ 3SAT ในเวลาพหุนาม (บน $T$ ตามความหมายเป็นต้น $H$โดยคำหลักของพวกเขา) แล้วแก้ไขโดยการแก้ 3SAT ในโพลีไทม์ทั้งบนไฮเพอร์โบลิกออโตเมตัน กล่าวอีกนัยหนึ่งผลลัพธ์หลักของบทความนี้ (ทฤษฎีบท 1) สามารถเขียนเป็น$NP_T \subseteq P_H$ในสัญกรณ์ของเรา สิ่งนี้ไม่ได้ให้วิธีแก้ปัญหา P เทียบกับ NP เพราะนั่นจะต้องเกี่ยวข้องกับคลาส$NP_T$ และ $P_T$.

โปรดทราบว่าผู้เขียนมีข้อสังเกตบางประการเกี่ยวกับปัญหา P เทียบกับ NP ในหัวข้อ 4.2 โดยที่พวกเขาอ้างว่าผลลัพธ์เป็นหลักฐานสำหรับ P$\neq$NP (!):