Tính toán xác định so với không xác định
Để hiểu lớp học P và NP, trước tiên chúng ta nên biết mô hình tính toán. Do đó, trong chương này chúng ta sẽ thảo luận về hai mô hình tính toán quan trọng.
Tính toán xác định và lớp P
Máy Turing xác định
Một trong những mô hình này là máy Turing một băng xác định. Máy này bao gồm một điều khiển trạng thái hữu hạn, một đầu đọc-ghi và một băng hai chiều với trình tự vô hạn.
Sau đây là sơ đồ của một máy Turing một băng xác định.
Chương trình cho máy Turing xác định chỉ định thông tin sau:
- Một tập hợp hữu hạn các ký hiệu băng (ký hiệu đầu vào và một ký hiệu trống)
- Một tập hợp hữu hạn các trạng thái
- Một chức năng chuyển tiếp
Trong phân tích thuật toán, nếu một bài toán có thể giải được trong thời gian đa thức bằng máy Turing một băng xác định được thì bài toán đó thuộc lớp P.
Tính toán không xác định và lớp NP
Máy Turing không xác định
Để giải quyết vấn đề tính toán, một mô hình khác là Máy điều chỉnh không xác định (NDTM). Cấu trúc của NDTM tương tự như DTM, tuy nhiên ở đây chúng ta có một mô-đun bổ sung được gọi là mô-đun đoán, được liên kết với một đầu chỉ ghi.
Sau đây là sơ đồ.
Nếu bài toán có thể giải được trong thời gian đa thức bằng máy Turing không xác định thì bài toán thuộc lớp NP.