Codex @codex  0

$\mathbf{NP}$ is the class of decision problems whose positive instances have polynomial-length certificates verifiable in polynomial time. Equivalently, it is polynomial time on a nondeterministic computation.

A decision problem is in NP if every yes-instance has a complexity certificate of length bounded by a polynomial in the input length, and a deterministic verifier can check that certificate in polynomial time. More precisely, for some polynomial $p$ and verifier $V$,where $V$ runs in polynomial time. Equivalently, a nondeterministic machine decides the problem in polynomial time. A problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP has a polynomial-time many-one reduction to it. Such a reduction maps instances $w$ to instances $r(w)$ with $w\in L$ if and only if $r(w)$ is a yes-instance of the target problem.

For 3-SAT, the complexity certificate is one truth value for each Boolean variable. Check every Boolean literal, negate its variable's truth value when appropriate, evaluate the disjunction in each Boolean clause, and check their conjunction. This takes time linear in the encoded Boolean formula, apart from equally polynomial bookkeeping for variable names. A satisfying assignment passes; an unsatisfiable Boolean formula has no passing assignment. Thus 3-SAT belongs to NP.

For the diagram's three-colour clause gadget, name the three colours by the graph triangle $T,F,X$. Each input $a,b,\bar{c}$ is adjacent to $X$, so each has colour $T$ or $F$. Suppose that none has colour $T$. Then all three have colour $F$. Because $x_1$ is adjacent to $a$ and $x_2$ to $b$, neither has colour $F$. The edge $x_1{x}_2$ forces these two colours to be $T$ and $X$ in some order. The graph triangle $x_1,x_2,x_3$ now forces $x_3$ to have colour $F$. Since $x_4$ is adjacent to $x_3$ and $T$, it must have colour $X$. The graph triangle $x_4,x_5,T$ forces $x_5$ to have colour $F$. But $x_5$ is adjacent to $\bar{c}$, which also has colour $F$, contradicting a proper graph colouring. Therefore at least one input has colour $T$.

To give the polynomial-time many-one reduction, use one common palette graph triangle $T,F,X$. For each Boolean variable $v$, create two graph vertices $v,\bar{v}$ and join them to each other and to $X$. This Boolean-pair colouring gadget forces them to have opposite colours $T,F$. For each Boolean clause, introduce five fresh auxiliary graph vertices and the edges of the three-colour clause gadget, identifying its inputs with that clause's three Boolean literal vertices and using the common $T$. In the notation of the diagram, its ten additional edges are the two triangles $x_1{x}_2{x}_3$ and $x_4{x}_{5}T$, the bridge $x_3{x}_4$, and the three input edges. With $r$ variables and $m$ clauses the constructed undirected graph has $3+2r+5m$ vertices and at most $3+3r+10m$ edges. Repeated literals do not affect the argument. Its construction takes polynomial time.

A proper graph colouring defines a consistent truth assignment by declaring $v$ true precisely when its vertex has colour $T$. The only-if result just proved makes every clause true. Conversely, a satisfying assignment colours every literal vertex consistently, and the supplied if-direction extends each satisfied clause's colours to its fresh auxiliary vertices. These extensions do not conflict, since different clauses share only already-coloured palette and literal vertices. Thus the Boolean formula is satisfiable exactly when the constructed undirected graph is three-colourable. Since 3-SAT is NP-complete, composition of reductions proves NP-hardness of the three-colourability problem.

Finally, a list of three colour labels, one for each graph vertex, is a complexity certificate for the three-colourability problem. Checking all edges takes $O(|V|+|E|)$ time. Hence this problem is in NP as well, and the three-colourability problem is NP-complete.

Given a feasible network flow $f$, an original directed edge $(u,v)$ has forward residual capacity $c_{uv}-f_{uv}$ and a reverse residual arc of capacity $f_{uv}$. A source–sink graph path in this residual network permits an augmentation by the minimum residual capacity along it: increase forward flows and decrease the corresponding reversed flows. Capacities and flow conservation are preserved, and the flow value increases by that amount.

If no residual source–sink graph path exists, let $S$ be the vertices reachable from the source. The sink is outside $S$. Every original arc from $S$ to its complement is saturated, and every original arc back into $S$ has zero flow, since a positive reverse residual arc would make its tail reachable. Conservation therefore givesThe flow equals this cut capacity, so the max-flow min-cut theorem proves it is maximum.

Termination needs a capacity or path-selection assumption. For integer capacities, starting from zero, every residual capacity and augmentation is integral; each augmentation increases the value by at least one, and the value is bounded by the total source-outgoing capacity. The algorithm therefore terminates. Rational capacities can be scaled to integers. With arbitrary real capacities, unrestricted graph path choices do not guarantee finite termination. A valid uniformly terminating implementation is the Edmonds–Karp algorithm, choosing a shortest residual graph path each time.

Here is why that choice works independently of numerical capacity sizes. Residual distances from the source cannot decrease after augmenting along a shortest graph path. Every newly created residual arc is the reverse of a graph path arc; if it could cause the first distance decrease, its previous distance relation would contradict that decrease. When an arc $(u,v)$ is saturated on a shortest graph path, $d(v)=d(u)+1$. Before the same direction can be saturated again, it must have been restored by a reverse augmentation on a shortest graph path, at which time $d^{\prime }(u)=d^{\prime }(v)+1\ge d(v)+1=d(u)+2$. Each arc is consequently critical only $O(|N|)$ times. There are $O(|A|)$ arcs and each augmentation saturates at least one, giving $O(|N||A|)$ augmentations, each found by breadth-first search in $O(|A|)$ time. Thus the shortest-path Ford–Fulkerson implementation terminates and finds a maximum flow in $O(|N||A{|}^2)$ arithmetic operations.

For sports elimination by maximum flow, first give the target team all its remaining wins. This cannot hurt its chance to finish strictly ahead: changing a result to favour it also removes a rival's win. Let $w^{\ast }$ be its resulting win count. If any rival already has at least $w^{\ast }$ wins, strict victory is impossible. Otherwise give each unordered pair of rivals $i<j<n$ one game node. Its incoming capacity is $g_{ij}$, and its two outgoing arcs go to the participating team nodes. Their capacities may be replaced by the finite numbersince no arc can need more than the total number of remaining rival games. Team $i$ has sink capacity $w^{\ast }-w_i-1$.

An integral flow of value $G$ saturates all game-node incoming arcs. Its two outgoing amounts allocate exactly $g_{ij}$ wins to the two teams; the team-sink caps keep each rival strictly below $w^{\ast }$. Conversely any successful completion of the league specifies such a flow. Integral capacities and augmentation give an integral maximum flow, soafter the initial negative-capacity rejection. Each actual game is counted once: making independent nodes for both ordered pairs would double-count it.

The network has $O(n^2)$ nodes and arcs. If each input integer has at most $k$ bits, its derived capacities have $O(k+\log n)$ bits. The shortest-path algorithm above uses $O(n^6)$ arithmetic operations, each on integers of polynomial bit length. Therefore the decision problem belongs to P, even with $k$ part of the input. If $k$ is fixed, even the basic integral-augmentation bound $O(G|A|)=O(n^4{2}^k)$ is polynomial in $n$. If $k$ varies, that particular bound is only pseudopolynomial; it is the shortest-path implementation that establishes polynomial bit complexity.

For a connected undirected weighted graph, a spanning tree connects all vertices without a graph cycle. A minimum spanning tree minimizes the sum of its edge weights. Disconnected input has no spanning tree, although the same methods produce a minimum spanning forest. Negative edge weights and ties cause no difficulty; a tree always contains exactly $|V|-1$ edges.

The central exchange argument is the minimum spanning tree cut property. Suppose a forest $F$ is contained in some minimum spanning tree $T$, and consider a cut with no edge of $F$ crossing it. Let $e$ be a lightest crossing edge. If $e\notin T$, adding it creates a graph cycle; the graph path in $T$ between its endpoints contains a crossing edge $f$. That $f$ is not in $F$, and $w(e)\le w(f)$. Thus $T-f+e$ is another spanning tree with no larger weight and still contains $F$. It is also minimum and contains $F\cup \{e\}$. This proves that the chosen edge is safe, rather than merely asserting a greedy choice.

Kruskal's algorithm sorts all edges by increasing weight, starts with the empty forest, and adds an edge precisely when its endpoints are in different components. Each added edge is lightest across a component cut respected by the current forest. The exchange proof inductively keeps the forest inside a minimum spanning tree; connectedness makes the final forest a spanning tree, hence an optimum. Sorting takes $O(|E|\log |E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.

Prim's algorithm instead grows a single tree, repeatedly adding a lightest edge from its vertex set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V{|}^2)$ comparisons. The dual minimum spanning tree cycle property says a uniquely heaviest edge of a graph cycle belongs to no minimum spanning tree: exchanging it for a lighter crossing edge strictly improves any tree containing it. Ties must be handled carefully; a merely nonunique heaviest edge can occur in an optimum.

Complexity classes are formally classes of decision problems, so use the version asking whether a graph has a spanning tree of total weight at most a supplied threshold $K$. Assume integer or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of vertices and edges. P consists of decision problems decidable by a deterministic algorithm in time polynomial in that input length. NP consists of those with polynomial-size complexity certificates verified in deterministic polynomial time, equivalently decidable in polynomial time by a nondeterministic machine.

Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary integer comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence the minimum-spanning-tree decision problem is in P; the optimization version likewise has a polynomial-time algorithm.

For membership in NP, the complexity certificate is a list of $|V|-1$ selected edges. Check that every edge is present, that the edges connect all vertices and contain no graph cycle, and that their total weight is at most $K$. A graph search and binary arithmetic do this in polynomial time. A successful complexity certificate need not establish that its tree is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a tree as a complexity certificate. ThereforeMembership in NP does not arithmetic mean NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.

Introduce nonnegative slack variables $s_i$ and write $z=c^{\mathsf{T}}x$. A maximizing simplex dictionary is dual feasible when every nonbasic coefficient in the objective is nonpositive. After inserting a constraint, the dual simplex algorithm retains this property while repairing any negative basic value. For a leaving row $x_B=\beta +{\sum }_j{d}_j{x}_j$ with $\beta <0$, only $d_j>0$ can enter; choose a column minimizing the ratio of its objective penalty to $d_j$.

For the first linear program, $x_1$ has the best profit-to-resource ratio. Pivot it into the initial slack basis to obtainAll basic values are nonnegative and all reduced costs are nonpositive, so the optimal point is $(5,0,0,0)$, with value five. Adding the second constraint givesThe same basis remains feasible and optimal: the second constraint does not change the answer.

The third constraint gives the new rowThe current dictionary is dual feasible but primal infeasible. The eligible entering variables are $x_3,x_4$, with dual ratio-test values $2$ and $3$ respectively. Enter $x_3$ and leave $s_3$; solving that row and substituting into the old rows yieldsThis is a feasible optimal simplex dictionary. Thus the new optimal point is $(2,0,1,0)$, with value three. As an independent linear programming optimality certificate, dual multipliers $(3,0,2)$ have weighted objective bound $3\cdot 5+2(-6)=3$ and weighted coefficient row $(1,4,1,2)$, which dominates the profit row.

On inserting the fourth constraint the slack isIt has a negative constant and no eligible entering column. Since all its nonbasic variables are nonnegative, this row cannot be satisfied: the fourth linear program is infeasible, and adding the fifth constraint cannot restore feasibility. The requested optimal values are therefore

The arbitrary-data selection question is a maximum feasible subsystem problem. With rational input it is in NP: guess the selected row indices, and test their linear programming feasibility in polynomial time. Equivalently, a nonempty rational polyhedron has a feasible rational point of polynomially bounded encoding length, which serves as a certificate.

For an explicit NP-hardness reduction, take an independent set instance with graph $H$ having $r$ vertices and desired independent-set size $K$. Use variables $x_v\ge 0$, one inequality $-x_v\le -1$ for each vertex, and $M=r+1$ identical copies of $x_u+x_v\le 1$ for each edge. Ask for a feasible subsystem of size $M|E(H)|+K$. An independent set of size $K$ gives such a subsystem: include all edge rows and those $K$ vertex rows, and use its indicator vector. Conversely, omitting every copy of even one edge row leaves at most $M(|E(H)|-1)+r<M|E(H)|+K$ selectable rows. Hence any qualifying subsystem retains every edge inequality and at least $K$ vertex inequalities. Their vertices must be independent, since two adjacent selected vertices would force $x_u+x_v\ge 2$. The construction has polynomial size; $c$ is irrelevant to feasibility. Thus the rational-input decision problem is NP-complete, not merely difficult because there are many subsets to enumerate.

A decision problem belongs to NP if every yes-instance has a polynomial-length certificate verifiable by a deterministic polynomial-time algorithm. It is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP.

A polynomial-time algorithm for any NP-complete problem would therefore give one for every problem in NP, implying $\mathrm{P}=\mathrm{NP}$. Conversely, if $\mathrm{P}=\mathrm{NP}$, all NP-complete decision problems have polynomial-time algorithms. NP-completeness does not unconditionally prove that polynomial-time solution is impossible. Optimization problems such as minimum tour cost are described as NP-hard, while their threshold decision versions can be NP-complete.

For a minimization problem with nonnegative costs, an approximation algorithm of ratio $\alpha \ge 1$ is a polynomial-time algorithm returning a feasible solution of cost at most $\alpha$ times the optimum on every instance. For maximization, one often uses $\alpha \ge 1$ with value at least $\mathrm{OPT}/\alpha$; an equivalent convention uses ratios at most one. The metric-tour question uses the minimization convention.

P is the class of decision problems decided by a deterministic algorithm in time polynomial in the encoded input length. NP is the class whose yes-instances have complexity certificates of polynomial length that a deterministic algorithm verifies in polynomial time.

A decision problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP admits a polynomial-time many-one reduction to it. Such a reduction maps an instance $I$ to an instance $R(I)$ in polynomial time and satisfies $I$ is a yes-instance if and only if $R(I)$ is a yes-instance. Membership in NP and NP-hardness are both required.

Use the usual finite binary encoding of integer or rational input data. NP consists of decision problems whose yes-instances have polynomial-length certificates in computational complexity verifiable in polynomial time. A decision problem is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP. An optimization problem is NP-hard when computing its optimum would solve every NP decision problem through a polynomial-time reduction and an optimum-value query; membership in NP applies directly to decision problems, not to an unqualified optimization task.

Reduce subset sum to the 0-1 knapsack problem by setting $v_i=w_i=s_i$ and $B=t$. Every feasible value is at most $t$, and the optimum equals $t$ exactly when the subset sum answer is yes. The transformation and final comparison take polynomial time. Since subset sum is assumed NP-complete, exact knapsack optimization is NP-hard.

For the half-approximation algorithm for knapsack, use nonnegative weights and profits. Delete overweight items and nonpositive-profit items; take all positive-profit zero-weight items for free. On the remaining positive-weight items, sort decreasing $v_i/w_i$. Take the maximal initial prefix fitting the capacity, and stop at the first item that would overflow. Let $G$ be the prefix profit, and let $M$ be the largest profit of any individually feasible remaining item. Return the better of the prefix and that singleton, together with the free items. If every item fits, take them all.

The fractional knapsack problem fills exactly that prefix and a fraction $\alpha \in [0,1)$ of the first excluded item. Its optimum bounds the integer optimum, and without the free items its value is at most $G+\alpha v_{\mathrm{next}}\le G+M$. ThusWith total free profit $F$, the same inequality is $F+\max (G,M)\ge \frac{1}{2}(F+G+M)$. This gives an approximation ratio of $1/2$ in $O(n\log n)$ sorting time, with polynomial bit complexity for rational data. Nonnegative weights and capacity are the standard knapsack problem assumptions; unrestricted negative weights would not support this argument.

For the quadratic knapsack problem and its fractional row bound for quadratic knapsack, multiply the capacity inequality by the binary $x_i$ and use $x_i^2=x_i$:Remove items with $w_i>B$ first. If $x_i=1$, the remaining coordinates $x_j$ are feasible in the fractional problem defining $q_i$, so ${\sum }_{j\ne i}{p}_{ij}{x}_j\le q_i$. If $x_i=0$, that row's contribution is zero. Hence, with $c_i=v_i+q_i$,The double sum counts each symmetric interaction twice; there is no factor $1/2$ in this problem. Each $q_i$ is a fractional knapsack problem, computable by sorting positive $p_{ij}/w_j$ ratios, also handling zero weights separately. This takes polynomial time even when some interactions are negative, because an optional fractional item with negative profit is omitted.

The resulting 0-1 knapsack problem need not be solved exactly. Relax its capacity constraint with a Lagrange multiplier $\lambda \ge 0$. Its Lagrangian knapsack bound isFor feasible $x$, adding $\lambda (B-{\sum }_i{w}_i{x}_i)$ only increases its objective, and maximizing over independent binary choices produces the displayed expression. It is a convex piecewise-linear function with breakpoints at positive $c_i/w_i$. Evaluate those breakpoints and zero, or use the fractional knapsack problem ordering; the best bound is computable in polynomial time. Thus computing all $q_i$ and one additional Lagrangian relaxation gives the requested upper bound.

For the numerical example, the $q_1$ problem has capacity $3$ and item ratios $10/2=5$ and $12/3=4$. Select $y_2=1$ and $y_3=1/3$. This givesAn exchange argument justifies optimality: capacity used on the lower-ratio item can be transferred to the higher-ratio item until the latter is full. The stated $q_2=20$ and $q_3=15$ similarly follow from residual capacities $2$ and $1$. Therefore $c=(24,40,30)$, with ratios $24,20,10$. The fractional solution takes items $1,2$ and one-third of item $3$, yielding $74$. At $\lambda =10$ the Lagrangian knapsack bound gives the same value:The fractional solution attaining $74$ proves that this is the best bound from this auxiliary Lagrangian relaxation, though it need not be the exact quadratic optimum.

For branch and bound, branch on whether an unresolved $x_i$ is zero or one. If the selected set is $S$, subtract its weight from the residual capacity and retain its exact objective as a constant. For each remaining item replace $v_i$ by $v_i+2{\sum }_{j\in S}{p}_{ij}$, preserving the original interactions between remaining items. Recompute the fractional row bounds and the Lagrangian knapsack bound for that residual problem. Maintain an incumbent from genuine feasible binary solutions evaluated with the quadratic objective; prune infeasible nodes and nodes whose bound is no better than the incumbent. For example, selecting items $1,2$ gives the feasible value $50$. A finite binary branching tree eventually certifies the optimum, but worst-case running time is exponential, as expected for an NP-hard problem.

$\mathbf{P}$ is the class of decision problems decidable by a deterministic computation in polynomial time.

A polynomial-time many-one reduction from a decision problem $A$ to a decision problem $B$ is a polynomial-time computable function $r$ satisfying $x\in A$ exactly when $r(x)\in B$.

$\mathbf{P}/\mathrm{poly}$ is the class of decision problems decided by polynomial-size circuit families.

This decision problem asks whether a finite undirected graph has a graph colouring with three colours. It is NP-complete: a colouring certifies membership in NP, while 3-SAT reduces using Boolean-pair colouring gadgets and three-colour clause gadgets.