P versus NP

You have a tangle of rules for a guest list. Checking a proposed list is easy. Must there also be a fast way to find a list that works—or decide that none can?[1] [2]

A proposed guest list can be checked rule by rule: if Ana may attend only when Cy does, inviting Ana without Cy fails. But how can we decide whether any list satisfies all the rules? The general question is whether checking a short proposed solution efficiently always comes with an efficient way to decide that a solution exists—or that none does.

The input is an encoded instance. Let n be its length in bits. Polynomial time means one algorithm has a worst-case running time bounded by C n^k for fixed constants C and k as n grows. Encoding matters: an n-bit integer can be near 2^n, so taking one step per unit of its numeric value is not a polynomial bound in its bit length. P contains the decision problems a deterministic algorithm can solve within a polynomial bound.

NP contains decision problems whose yes-instances have polynomial-length certificates verifiable in polynomial time by a deterministic algorithm. For SAT, which asks whether a logical formula can be made true, a certificate assigns true or false to each variable; evaluating the formula checks it. The definition requires no analogous certificate for no-instances. P ⊆ NP, since a verifier can simply run the solving algorithm. NP stands for nondeterministic polynomial time; the name does not assert that its problems require nonpolynomial time.[2]

No proof settles whether fast checking always comes with fast solving. Trying every possible answer can be slow, but that does not show that every clever method must be slow.[1] [2]

General 3-SAT is NP-complete: it belongs to NP, and every NP decision problem can be translated into it in polynomial time while preserving the yes/no answer. A polynomial-time 3-SAT algorithm would establish P = NP; proving that none solves all instances would establish P ≠ NP. NP-completeness is a property of a whole problem family, not a theorem that each instance is difficult.

A separation proof must exclude every polynomial-time algorithm, including methods nobody has discovered. Exponential brute-force search only describes one method. Another possible route is to show that an explicit NP problem needs Boolean circuits larger than every polynomial in input length. Such unrestricted lower bounds would suffice; lower bounds confined to a restricted circuit model do not generally establish the needed separation.[1] [2]

Many useful tasks involve finding a plan that satisfies rules. An answer would tell us whether difficulty finding such plans can reflect a fundamental limit, rather than a missing algorithm.[2]

For a satisfiable SAT formula, a yes/no solver can construct an answer. Set one variable true and ask whether the remaining formula is satisfiable; if not, set it false. Repeat while preserving satisfiability. A polynomial number of calls turns a polynomial-time decision procedure into a polynomial-time search procedure. This is why the formal yes/no question reaches tasks needing an actual plan or proof.

The cryptographic consequences also require care. P = NP would imply polynomial-time integer factoring, for example, but the cost of a concrete algorithm would determine its immediate practical impact. P ≠ NP alone would not prove a particular cryptographic scheme secure: hardness in the worst case does not establish hardness on the inputs an attacker encounters.[2]