Hartmanis–Stearns conjecture

The conjecture that P differs from NP: some problems with polynomial-time verifiable solutions cannot be solved in polynomial time.

Connect

P (complexity): The class of decision problems solvable by a deterministic algorithm in polynomial time. This is the class the conjecture says is smaller than NP.
NP-complete problem: A problem in NP to which every problem in NP reduces in polynomial time. If any NP-complete problem is in P, then P equals NP.
Juraj H. Hartmanis: A theoretical computer scientist who helped establish computational complexity theory. His work with Stearns helped frame resource-bounded computation and the P-versus-NP question.
Relativization: A proof technique that gives algorithms access to an oracle while preserving their formal structure. Relativizing arguments cannot settle P versus NP because oracles yield opposite outcomes.
NP (complexity): The class of decision problems whose yes-instances have certificates verifiable in polynomial time. The conjecture asks whether NP contains problems outside P.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete. It identifies SAT as a single problem whose polynomial-time solution would settle the conjecture negatively.
Richard E. Stearns: A computer scientist whose work helped develop formal measures of computational complexity. His collaboration with Hartmanis established foundational time-complexity methods.
Natural proofs: A framework identifying properties of Boolean functions that make certain circuit lower-bound arguments powerful and constructive. Under standard cryptographic assumptions, natural proofs cannot establish the circuit lower bounds needed for a separation.
Polynomial time: A computational resource bound in which running time grows as a polynomial of input length. It defines the efficiency threshold shared by P and NP.
Cryptography: The study and practice of securing information through mathematical techniques. Many cryptographic schemes rely on computational hardness, though P ≠ NP alone would not guarantee their security.