Giải thuật - Giải Thuật Xấp Xỉ

° Nếu một bài toán là NP-đầy đủ thì không chắc rằng ta sẽ tìm được một giải thuật thời gian đa thức để giải nó một cách chính xác.
° Tiếp cận một bài toán NP-đầy đủ
1) Nếu các input có kích thước nhỏ thì một giải thuật chạy trong thời gian số mũ vẫn có thể thoả mãn yêu cầu
2) Thay vì tìm các lời giải tối ưu, có thể tìm các lời giải gần tối ưu trong thời gian đa thức.