NP-hardness

A decision problem is NP-hard when every problem in NP polynomial-time many-one reduces to it.

A decision problem is NP-complete when it is both in NP and NP-hard.

Given subsets $S_1,\dots ,S_m$ of a finite universe, the decision problem asks whether at most $k$ of them cover the universe. It is NP-complete. If $k<m$, existence of a cover by at most $k$ subsets is equivalent to existence of a cover by exactly $k$, by adding unused subsets. The promise that every element occurs in some subset loses no hardness: an uncovered element can be detected in polynomial time and mapped to a fixed negative instance.

// Target: mathematical-optimization.bigb

Assume $2\le k<m$ and ${\bigcup }_i{S}_i=S$. Construct a two-player game with row $i$ for $S_i$ and columns $0,1,\dots ,n$. Column $0$ pays both players one; column $j>0$ pays $(1,0)$ when $j\in S_i$, and $(0,k/(k-1))$ otherwise. There is a Nash equilibrium whose row player's support of a mixed strategy has size $k$ exactly when $k$ rows cover the universe. A uniform mixture on a cover makes column $0$ a best response. Conversely, if some element is uncovered by the support, the column player's best responses are uncovered elements and the row player's current payoff is zero. The union promise provides a profitable row deviation. Without the union promise the equivalence is false: a globally uncovered element is a best response against every row mixture.

// Target: mathematical-optimization.bigb

Every NP verifier can be compiled into a polynomial-size Boolean circuit whose inputs encode its certificate, and then into an equisatisfiable conjunctive normal form by a Tseitin transformation. This gives a polynomial-time many-one reduction from every NP language to SAT. Checking a guessed assignment proves membership, so SAT is NP-complete.

Given finitely encoded nonnegative integers $s_i$ and target $t$, the subset sum problem asks whether some subset sums to $t$. Taking equal item weights and profits reduces it to testing whether a 0-1 knapsack problem with capacity $t$ attains value $t$.

The Boolean satisfiability problem asks whether a Boolean formula has an assignment making it true.

Encode each truth value by $t_k\in \{0,1\}$. A positive Boolean literal has value $t_k$ and its negation has value $1-t_k$. The sum of literal values in a clause is at least one exactly when that clause is true. Thus the displayed inequalities, with objective zero, express Boolean satisfiability as a binary integer programming feasibility problem. For maximum satisfiability, introduce $q_i\in \{0,1\}$ with $q_i\le {\sum }_{\ell \in C_i}{L}_{\ell }(t)$ and maximize ${\sum }_i{q}_i$. False clauses force zero indicators; true clauses permit indicators one, and maximization selects all of them. Hence the optimal objective equals the maximum number of true clauses.

Maximum satisfiability asks for a truth assignment maximizing the number of true clauses of a conjunctive normal form formula. The Boolean satisfiability problem asks whether all its clauses can be made true. Binary clause indicators give an integer programming formulation, and the literal-frequency greedy approximation for MAX-SAT guarantees at least half the optimum. Counts of clauses, rather than multiplicities of repeated literals within one clause, are relevant to this objective.

In the residual unsatisfied formula, choose a Boolean literal contained in the largest number $a$ of clauses and make it true. Its opposite occurs in at most $a$ clauses, since it too was an eligible literal. The step permanently satisfies $a$ clauses; only clauses containing the opposite can become empty, so it loses at most $a$ clauses. Delete satisfied clauses and false literals and repeat. No satisfied clause or newly empty clause is counted twice. Summing gives total lost nonempty clauses at most total satisfied clauses $G$. All initially nonempty clauses are eventually in one of these classes, so $G\ge N_{+}/2\ge \mathrm{OPT}/2$. Initial empty clauses can never be satisfied and are excluded from $N_{+}$. This proves the approximation algorithm guarantee even with tautological clauses or repeated literals.

Satisfiability of conjunctive normal form formulas whose clauses have at most two unnegated variables. It is NP-complete: binary AND/OR and unary NOT gate equivalences in a Tseitin transformation already satisfy that restriction. Clauses may contain arbitrarily many negative literals; the total clause width is not restricted to two.

Maximum 2-satisfiability asks for an assignment satisfying as many clause occurrences as possible when every nonempty clause has at most two literals. Occurrences are counted even when a clause is repeated. Its decision problem is NP-complete by the seven-clause gadget for MAX-2SAT, while the method of conditional probabilities gives a polynomial-time half approximation.

When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability $p>1/2$ and choose independent variables. Every proper binary clause is then satisfied with probability at least $1-p^2$, and every singleton with probability $p$. Maximize the common lower bound by $p=1-p^2$, giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio $p$. Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.

A three-literal disjunction can be represented by ten unit or two-literal clause occurrences with one fresh auxiliary variable. If the number $r$ of true input literals is zero, the best auxiliary choice satisfies six; for $r=1,2,3$, the best count is seven. Applying separate gadgets to all clauses of a 3-SAT instance gives target seven times the original clause count, proving NP-completeness of the decision form of MAX-2SAT. The local counting argument is essential: no gadget may exceed seven and compensate for an unsatisfied input clause.

A Boolean formula is a finite expression built from Boolean variables and Boolean operations. A choice of truth values determines its value. The Boolean satisfiability problem asks whether some choice makes it true.

A Boolean formula is in disjunctive normal form when it is a disjunction of conjunctions of Boolean literals. Width bounds the number of literals in each conjunction, not the number of conjunctions. A depth-$s$ decision tree gives such a formula of width at most $s$ by taking the disjunction of its accepting leaf conditions; rejecting leaves give the dual conjunctive normal form.

A Boolean formula is in conjunctive normal form when it is a conjunction of Boolean clauses. It is true precisely when every clause is true; an empty conjunction is true. 3-SAT restricts each clause to at most three Boolean literals.

Introduce a Boolean variable for each gate output and impose its equivalence to the gate's input function with a constant number of clauses. A final unit clause forces acceptance. For a bounded-fan-in Boolean circuit, the formula size is linear in the gate count and it is satisfiable exactly when some input makes the Boolean circuit output one. Auxiliary variables extend the satisfying assignments; this is equisatisfiability, not equality as functions of the enlarged variable set.

A clause is an expression ${\ell }_1\vee \cdots \vee {\ell }_k$ formed from Boolean literals, true when at least one literal is true. The empty clause is false. Repeating a literal does not change the truth value. A conjunctive normal form formula is a conjunction of these clauses.

A Boolean literal is a Boolean variable $u$ or its negation $\neg u$. The two literals have opposite truth values. A Boolean clause combines literals, and a Boolean-pair colouring gadget represents a variable and its negation by two vertices with opposite Boolean colours.

A Boolean variable takes one of two truth values. It is an input to a Boolean formula; a Boolean literal uses the variable either positively or negated.

3-SAT is the Boolean satisfiability problem restricted to Boolean formulas in conjunctive normal form with at most three Boolean literals per Boolean clause. It is NP-complete. A nonempty short Boolean clause can be padded to three positions by repeating a Boolean literal, without changing satisfiability.

A Horn clause is a disjunction of literals containing at most one positive literal. It can be read as an implication whose antecedent is a conjunction of variables.

Horn-SAT asks whether a conjunction of Horn clauses is satisfiable.

The Horn-SAT forward-chaining algorithm starts with every variable false and repeatedly makes the conclusion of any enabled implication true. It reports failure if it enables a clause with no positive conclusion; otherwise the fixed point is the least satisfying assignment.

Quadratic-equation satisfiability over ${\mathbb{F}}_2$ asks whether a finite system of polynomial equations of degree at most two over the finite field ${\mathbb{F}}_2$ has a common solution.

If $\mathbf{P}\ne \mathbf{NP}$, then NP contains a decision problem that is neither in P nor NP-complete.