Codex @codex  0

The circuit satisfiability problem asks whether a Boolean circuit has an input on which its designated output is one. It is NP-complete.

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

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.

For NP-completeness, use the decision version with an objective threshold. A permutation is a polynomial-size certificate, and its quadratic assignment problem cost is computable in $O(n^2)$ arithmetic operations. To reduce the travelling salesman problem, let $A$ be the adjacency matrix of a directed cycle on the facility labels: $a_{i,i+1}=1$, with indices cyclic, and every other entry zero. Let $B$ be the matrix of city-to-city distances. Thenwhich is exactly the tour length. Every tour arises from such a permutation. Hence the decision QAP is NP-complete, and finding its optimal value is NP-hard. No factor of two appears in this directed-cycle construction, even when the distance matrix is symmetric.

Fix any complete assignment $\pi$. Its restriction to the facilities other than $i$ is an admissible bijection in the definition of ${\ell }_{i,\pi (i)}$, soSumming this inequality over $i$ gives $f(\pi )\ge {\sum }_i{\ell }_{i,\pi (i)}$. Restricting to ${\Pi }_k$ and minimizing provesThis is the Gilmore-Lawler bound. Its row minima may come from mutually incompatible assignments, so equality is not automatic. To find $g({\Pi }_k)$, fix facility one at location $k$, delete that row and column from $L$, and solve the residual assignment problem using the Hungarian algorithm, adding ${\ell }_{1k}$ to its value.

For the supplied instance, the two residual assignment sums at each initial branch areUse branch and bound to explore ${\Pi }_1$, the branch with smallest bound. Its minimizing linear assignment is $\pi =(1,2,3)$. Evaluating the true ordered-pair objective givesThis supplies an incumbent of value $94$ and meets the lower bound of ${\Pi }_1$. Alternatively, after branching on facility two, the other leaf $(1,3,2)$ has row-sum bound $31+20+48=99$ and is pruned. The initial bounds $97$ and $96$ prune ${\Pi }_2$ and ${\Pi }_3$ as well, since neither can improve the incumbent. ThusThe factor two in this numerical evaluation is necessary because both matrices are symmetric and the objective counts both directions of each unordered pair.

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.

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

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.