The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.
Ladner's theorem 2026-09-24
If , then NP contains a decision problem that is neither in P nor NP-complete.