Tên của một vấn đề đáp ứng khẳng định của Ladner là gì?
Ladner đã chỉ ra rằng nếu P ≠ NP thì tồn tại các bài toán trong NP không nằm trong P cũng không phải là NP-đầy đủ. Những bài toán như vậy được gọi là bài toán trung gian NP. Bài toán đẳng cấu đồ thị, bài toán logarit rời rạc và bài toán phân tích thành nhân tử là những ví dụ về các bài toán được cho là NP-trung gian. Chúng là một số trong số rất ít bài toán NP không nằm trong P hoặc là NP-đầy đủ.
NP-vấn đề trung gian