Karp–Lipton theorem

The Karp–Lipton theorem is an important result in computational complexity theory that connects the complexity classes \(P\), \(NP\), and \(PSPACE\). It was established by Richard Karp and Richard J. Lipton in the early 1980s. The theorem states that if \(NP\) problems can be solved in polynomial time by a non-deterministic Turing machine using polynomial space (i.e.