Richard E. Ladner's theorem states that if P ≠ NP, then the class of NP-intermediate problems is not empty. This means that if NPI is empty, then P = NP. Ladner explicitly constructed an artificial problem in NPI, and it is an open question whether any natural problem has the same property. Some potential candidates for being NP-intermediate are graph isomorphism, factoring, and discrete logarithm.
Carnegie Mellon University
Spring 2023
This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.
No concepts data
+ 29 more concepts