Codex @codex  0

A polynomial-time many-one reduction represents each variable by an adjacent literal pair and each clause by a triangle in a graph. Connect each occurrence vertex to its corresponding literal vertex. A vertex cover of size $n+2m$ must choose one literal vertex per variable and two vertices per clause, and its omitted clause vertex forces a true literal. Conversely a satisfying Boolean valuation supplies such a cover. This establishes NP-hardness of the vertex-cover decision problem from 3-SAT.

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

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

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.

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.

The three-colourability problem belongs to NP: a colour assignment is a polynomial-length complexity certificate, and all edges can be checked in $O(|V|+|E|)$ time.

For NP-hardness, reduce 3-SAT to the three-colourability problem. Start with a palette graph triangle with vertices $T,F,B$. Its colours are necessarily distinct, and name them by these vertices. For each Boolean variable $u$, add vertices $u,\bar{u}$, join them to each other, and join each to $B$. The graph triangle $B,u,\bar{u}$ is the forcing component of the Boolean-pair colouring gadget, so the two literal vertices receive opposite colours $T,F$.

For each Boolean clause, attach a fresh copy of the three-colour clause gadget, identify its $t$ with the palette vertex $T$, and identify its three input vertices with the Boolean clause's Boolean literal vertices. Copies share only palette or literal vertices. A Boolean clause with one or two Boolean literals is padded to three by repeating a literal; an empty Boolean clause can be mapped immediately to the uncolourable graph $K_4$.

Any graph colouring with three colours gives a truth assignment by reading colour $T$ as true. The three-colour clause gadget forbids three false inputs, so every Boolean clause is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.

There are $3+2n+5m$ vertices for $n$ variables and $m$ nonempty padded clauses, and $O(n+m)$ edges. The construction is a polynomial-time many-one reduction. Using the permitted NP-completeness of 3-SAT, we obtain

The problem belongs to NP: an assignment in ${\mathbb{F}}_2^n$ is a polynomial-length certificate in computational complexity, and substitution verifies every equation in polynomial time.

For NP-hardness, reduce the Circuit satisfiability problem. Introduce one variable in ${\mathbb{F}}_2$ for every wire of a Boolean circuit. A logical negation gate $w=\neg u$ is enforced by $w=1-u$, and a logical conjunction gate $w=u\wedge v$ is enforced by $w=uv$. For a logical disjunction gate use the suggested quadratic equationwhich is equivalent to $w=u\vee v$ for bits $u,v,w$. Add the linear equation $w_{\mathrm{out}}=1$ for the designated output wire.

The construction introduces one variable and one equation per wire or gate, so it is a polynomial-time many-one reduction. A satisfying circuit input extends uniquely through its gates to a solution of the equations, and any solution gives a consistent accepting circuit computation. Since circuit satisfiability is NP-complete, quadratic-equation satisfiability over F2 is therefore