การคำนวณเชิงกำหนดกับ Nondeterministic
เพื่อทำความเข้าใจในชั้นเรียน P และ NPอันดับแรกเราควรทราบรูปแบบการคำนวณ ดังนั้นในบทนี้เราจะพูดถึงโมเดลการคำนวณที่สำคัญสองแบบ
การคำนวณเชิงกำหนดและคลาส P
เครื่องทัวริงที่มุ่งมั่น
หนึ่งในโมเดลเหล่านี้คือเครื่องทัวริงแบบเทปเดียวที่กำหนดได้ เครื่องนี้ประกอบด้วยตัวควบคุมสถานะ จำกัด หัวอ่านเขียนและเทปสองทางที่มีลำดับไม่สิ้นสุด
ต่อไปนี้เป็นแผนผังของเครื่องทัวริงแบบเทปเดียวที่กำหนดได้
โปรแกรมสำหรับเครื่องทัวริงที่กำหนดได้ระบุข้อมูลต่อไปนี้ -
- ชุดสัญลักษณ์เทป จำกัด (สัญลักษณ์อินพุตและสัญลักษณ์ว่าง)
- ชุดสถานะที่ จำกัด
- ฟังก์ชันการเปลี่ยนแปลง
ในการวิเคราะห์อัลกอริทึมถ้าปัญหาสามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องทัวริงเทปที่กำหนดได้ปัญหาจะเป็นของคลาส P
Nondeterministic Computation และ Class NP
เครื่องทัวริงที่ไม่แน่นอน
ในการแก้ปัญหาด้านการคำนวณอีกรุ่นหนึ่งคือเครื่องทัวริงแบบไม่กำหนดปัจจัย (NDTM) โครงสร้างของ NDTM นั้นคล้ายกับ DTM แต่ที่นี่เรามีโมดูลเพิ่มเติมอีกหนึ่งโมดูลที่เรียกว่าโมดูลการเดาซึ่งเกี่ยวข้องกับหัวเขียนอย่างเดียว
ต่อไปนี้เป็นแผนผัง
หากปัญหาสามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องทัวริงที่ไม่ได้กำหนดปัจจัยปัญหาจะเป็นของคลาส NP