Nếu P = NP là không giải được, và phép rút gọn được áp dụng cho một bài toán NP-đầy đủ đã biết so với Π2 đến Π1, có thể rút ra kết luận gì cho Π1?
Nếu một bài toán X nằm trong C và khó đối với C, thì X được coi là bài toán hoàn chỉnh đối với C. Điều này có nghĩa là X là bài toán khó nhất trong C. (Vì nhiều bài toán có thể khó như nhau, người ta có thể nói rằng X là một trong những bài toán khó nhất trong C.) Do đó, lớp bài toán NP-đầy đủ chứa các bài toán khó nhất trong NP, theo nghĩa là chúng là những bài toán có nhiều khả năng không nằm trong P. Bởi vì bài toán P = NP không được giải quyết, việc có thể rút gọn một bài toán NP-đầy đủ, Π2, thành một bài toán khác, Π1, sẽ chỉ ra rằng không có lời giải thời gian đa thức nào cho Π1. Điều này là do một lời giải thời gian đa thức cho Π1 sẽ mang lại một lời giải thời gian đa thức cho Π2. Tương tự, bởi vì tất cả các bài toán NP có thể được rút gọn về tập hợp, việc tìm thấy một bài toán NP-đầy đủ có thể được giải quyết trong thời gian đa thức có nghĩa là P = NP.
Không có lời giải thời gian đa thức nào được biết đến.