การคำนวณเชิงกำหนดกับ Nondeterministic

เพื่อทำความเข้าใจในชั้นเรียน P และ NPอันดับแรกเราควรทราบรูปแบบการคำนวณ ดังนั้นในบทนี้เราจะพูดถึงโมเดลการคำนวณที่สำคัญสองแบบ

การคำนวณเชิงกำหนดและคลาส P

เครื่องทัวริงที่มุ่งมั่น

หนึ่งในโมเดลเหล่านี้คือเครื่องทัวริงแบบเทปเดียวที่กำหนดได้ เครื่องนี้ประกอบด้วยตัวควบคุมสถานะ จำกัด หัวอ่านเขียนและเทปสองทางที่มีลำดับไม่สิ้นสุด

ต่อไปนี้เป็นแผนผังของเครื่องทัวริงแบบเทปเดียวที่กำหนดได้

โปรแกรมสำหรับเครื่องทัวริงที่กำหนดได้ระบุข้อมูลต่อไปนี้ -

  • ชุดสัญลักษณ์เทป จำกัด (สัญลักษณ์อินพุตและสัญลักษณ์ว่าง)
  • ชุดสถานะที่ จำกัด
  • ฟังก์ชันการเปลี่ยนแปลง

ในการวิเคราะห์อัลกอริทึมถ้าปัญหาสามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องทัวริงเทปที่กำหนดได้ปัญหาจะเป็นของคลาส P

Nondeterministic Computation และ Class NP

เครื่องทัวริงที่ไม่แน่นอน

ในการแก้ปัญหาด้านการคำนวณอีกรุ่นหนึ่งคือเครื่องทัวริงแบบไม่กำหนดปัจจัย (NDTM) โครงสร้างของ NDTM นั้นคล้ายกับ DTM แต่ที่นี่เรามีโมดูลเพิ่มเติมอีกหนึ่งโมดูลที่เรียกว่าโมดูลการเดาซึ่งเกี่ยวข้องกับหัวเขียนอย่างเดียว

ต่อไปนี้เป็นแผนผัง

หากปัญหาสามารถแก้ไขได้ในเวลาพหุนามโดยเครื่องทัวริงที่ไม่ได้กำหนดปัจจัยปัญหาจะเป็นของคลาส NP