ในทฤษฎีความซับซ้อนเชิงคำนวณ การลดเวลาพหุนามคือ วิธีการแก้ปัญหาหนึ่งโดยใช้วิธีอื่น การลดเวลาพหุนามมักใช้ในทฤษฎีความซับซ้อนเพื่อกำหนดทั้งคลาสความซับซ้อนและปัญหาที่สมบูรณ์สำหรับคลาสเหล่านั้น …
อะไรถือเป็นเวลาพหุนาม
อัลกอริธึมกล่าวกันว่าเป็นเวลาพหุนาม ถ้าเวลาทำงานของมันถูกขอบเขตบนด้วยนิพจน์พหุนามในขนาดของอินพุตสำหรับอัลกอริทึม นั่นคือ T(n)=O(nk) สำหรับค่าคงที่ที่เป็นบวก k
คุณจะรู้ได้อย่างไรว่าสิ่งใดเป็นพหุนามพหุนาม
3 คำตอบ. อัลกอริธึมเป็นแบบพหุนาม (มีเวลาทำงานแบบพหุนาม) ถ้าสำหรับ k, C>0 บางตัว เวลาทำงานของอินพุตขนาด n จะอยู่ที่ Cnk มากที่สุด ในทำนองเดียวกัน อัลกอริธึมเป็นพหุนามถ้าสำหรับ k>0 บางตัว เวลาทำงานของอินพุตขนาด n คือ O(nk)
จะเกิดอะไรขึ้นหากลดเวลาแบบเอ็กซ์โปเนนเชียลได้
หากอนุญาตให้ลดเวลาแบบเอกซ์โปเนนเชียล มันสามารถแก้ปัญหาเดิมได้อย่างเต็มที่และสร้างตัวอย่างปัญหาเล็กๆ น้อยๆ ของเป้าหมาย ซึ่งหมายความว่าทุกปัญหาใน NP จะลดให้ทุก ปัญหาอื่นๆ จากการลดลงดังกล่าว ดังนั้นทุกปัญหาใน NP จึงสมบูรณ์ NP สำหรับการลดเวลาแบบเอ็กซ์โปเนนเชียล
อัลกอริทึมเลขชี้กำลังคืออะไร
อัลกอริธึมกล่าวกันว่าเป็นเวลาเลขชี้กำลัง ถ้า T(n) อยู่บนขอบบนด้วย 2poly( ) โดยที่ poly(n) คือพหุนามบางตัวใน n อย่างเป็นทางการมากขึ้น อัลกอริทึมเป็นเวลาชี้แจงถ้า T(n) ถูกล้อมรอบด้วย O(2nk) สำหรับค่าคงที่บางค่า k. Ref:Wiki