อ่าน 1 นาที
NP-easy
ใน ทฤษฎีความซับซ้อน กลุ่ม ความซับซ้อน NP-easy คือเซตของ ปัญหาฟังก์ชัน ที่สามารถแก้ไขได้ใน เวลาพหุนาม โดย เครื่องจักรทัว ริ งเชิงกำหนด ที่มี ออราเคิล สำหรับ ปัญหาการตัดสินใจ...
NP-easy
ในทฤษฎีความซับซ้อนกลุ่มความซับซ้อนNP-easyคือเซตของปัญหาฟังก์ชันที่สามารถแก้ไขได้ในเวลาพหุนาม โดย เครื่องจักรทัว ริ งเชิงกำหนดที่มีออราเคิลสำหรับปัญหาการตัดสินใจ บางอย่าง ในNP
กล่าวอีกนัยหนึ่ง ปัญหา X เป็นปัญหา NP-easy ก็ต่อเมื่อมีปัญหา Y บางอย่างใน NP ที่ X สามารถลดรูป Turing ได้ในเวลาพหุนามไปยัง Y [ 1 ] ซึ่งหมายความว่าเมื่อกำหนดออราเคิลสำหรับ Y แล้ว จะมีอัลกอริทึมที่แก้ปัญหา X ได้ในเวลาพหุนาม (อาจโดยการใช้ออราเคิลนั้นซ้ำๆ)
NP-easy เป็นอีกชื่อหนึ่งของ FP NP (ดู บทความ เกี่ยวกับปัญหาฟังก์ชัน ) หรือ FΔ 2 P (ดู บทความ เกี่ยวกับลำดับชั้นของพหุนาม )
ตัวอย่างของปัญหา NP-easy คือปัญหาการเรียงลำดับรายการสตริง ปัญหาการตัดสินใจที่ว่า "สตริง A มากกว่าสตริง B หรือไม่" อยู่ในกลุ่ม NP มีอัลกอริทึมอย่างเช่นquicksortที่สามารถเรียงลำดับรายการได้โดยใช้การเรียกใช้ฟังก์ชันเปรียบเทียบเพียงจำนวนพหุนาม บวกกับการทำงานเพิ่มเติมอีกจำนวนพหุนาม ดังนั้น การเรียงลำดับจึงเป็นปัญหา NP-easy
นอกจากนี้ยังมีปัญหาที่ยากกว่าแต่ยังเป็นปัญหา NP-easy อีกด้วย ดูตัวอย่างได้ที่ NP-equivalent
นิยามของ NP-easy ใช้การลดรูปทัวริง (Turing reduction)แทนการลดรูปหลายต่อหนึ่ง (many-one reduction)เพราะคำตอบของปัญหาYมีเพียง TRUE หรือ FALSE เท่านั้น แต่คำตอบของปัญหาXสามารถเป็นแบบทั่วไปได้มากกว่า ดังนั้นจึงไม่มีวิธีทั่วไปที่จะแปลงกรณีของXไปเป็นกรณีของYที่ให้คำตอบเดียวกันได้
หมายเหตุ
- ↑แกรีย์ แอนด์ จอห์นสัน (1979) , p. 117, 120.
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ NP-easy
ใน ทฤษฎีความซับซ้อน กลุ่ม ความซับซ้อน NP-easy คือเซตของ ปัญหาฟังก์ชัน ที่สามารถแก้ไขได้ใน เวลาพหุนาม โดย เครื่องจักรทัว ริ งเชิงกำหนด ที่มี ออราเคิล สำหรับ ปัญหาการตัดสินใจ...
หมายเหตุ
↑ แกรีย์ แอนด์ จอห์นสัน (1979) , p. 117, 120. ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=NP-easy&oldid=1222934034 "