Có những bài toán thực tế mà cho đến nay vẫn chưa xây dựng được thuật toán hiệu quả để giải (đó là thuật toán có độ phức tạp tính toán là đa thức) và chứng minh được mức độ khó thực chất của nó. | PHỤ LỤC CÁC LỚP P VÀ NP VÀ LỚP CÁC BÀI TOÁN NP-ĐẦY ĐỦ Có những bài toán thực tế mà cho đến nay vẫn chưa xây dựng được thuật toán hiệu quả để giải đó là thuật toán có độ phức tạp tính toán là đa thức và chứng minh được mức độ khó thực chất của nó. Trong số các bài toán như vậy có thể kể ra các bài toán nổi tiếng sau Bài toán người du lịch Bài toán chu trình Hamilton Bài toán tô màu đồ thị Bài toán tìm đường đi đơn dài nhất của đồ thị. Ta có thể quy lỗi cho việc thiết kế và phân tích thuật toán hay lý thuyết độ phức tạp hay không Liệu trên thực tế có thuật toán hiệu quả để giải quyết các bài toán này không Trong phần này ta sẽ có một kết quả nổi tiếng mỗi thuật toán hiệu quả để giải một trong số các bài toán vừa kể trên sẽ cũng cho ta thuật toán hiệu quả để giải tất cả các bài toán còn lại. Ta chưa biết những bài toán này là dễ hay khó giải nhưng ta biết rằng tất cả chúng có độ phức tạp như nhau. Ý nghĩa thực tế quan trọng của các bài toán này là đảm bảo rằng mỗi một bài toán này là đối tượng của những cố gắng tìm thuật toán hiệu quả để giải. 1. LỚP P VÀ LỚP NP. . Định nghĩa Cho M là một máy Turing. Hàm T n được gọi là độ phức tạp tính toán của M nếu với mọi xâu vào 0 có độ dài n thì đều tồn tại một dãy hình trạng có nhiều nhất là T n bước đoán nhận 0 ở đây T n là một số nguyên dương . Nếu có một xâu nào đó có độ dài n mà máy Turing không dừng thì đối với n đó T n không xác định. . Định nghĩa Lớp P là lớp các ngôn ngữ được đoán nhận bởi máy Turing đơn định và độ phức tạp tính toán là đa thức. Có thể phát biểu một cách khác là một bài toán được coi là thuộc lớp P nếu tồn tại một thuật toán đa thức để giải nó. Người ta nói rằng những bài toán thuộc lớp P là dễ. . Chú ý Theo quan điểm toán học lớp P là rất tự nhiên. Điều này thấy được từ việc nó là bất biến cao đối với mô hình tính toán được dùng. Chẳng hạn các máy Turing M1 với nhiều băng là nhanh hơn các máy Turing thông thường tức là độ phức tạp tính toán của chúng nhận các giá trị nhỏ hơn. Tuy nhiên nếu độ
