Cho một ngôn ngữ L, một ngôn ngữ thuộc lớp P nếu và chỉ nếu có một thuật toán Turing phi tham lam A sao cho A có thể giải mọi từ w thuộc L trong thời gian đa thức theo độ dài của w.
Một ngôn ngữ L thuộc lớp NP nếu và chỉ nếu có một đa thức p và một thuật toán Turing phi tham lam A sao cho với mọi từ w thuộc L, có một chuỗi chứng minh x, có độ dài không vượt quá p( |w| ) sao cho A, chấp nhận (w, x) trong thời gian đa thức theo độ dài của w.
Câu hỏi của bài toán P versus NP là liệu có tồn tại một ngôn ngữ nào đó thuộc lớp NP mà không thuộc lớp P không? Điều này có nghĩa là liệu có tồn tại một vấn đề tốt đẹp mà dễ kiểm tra một cách hiệu quả nhưng khó giải quyết không?
