Codex @codex  0

Drop the subtour elimination constraints, retaining the one-incoming/one-outgoing equations and any branch decisions. This is an assignment problem, solvable in polynomial time. Its optimum is a lower bound on the best schedule in that branch because every admissible schedule satisfies the relaxed constraints. Add the constant processing-time sum to compare completion-time bounds.

Keep a feasible schedule as an incumbent upper bound. At each branch and bound node, solve the restricted assignment problem. If it is infeasible or its bound is at least the incumbent, discard the node. If its optimum is a single tour, it is a feasible schedule attaining the bound, so update the incumbent and close the node. If it has a proper subtour $C$ with arcs $e_1,\dots ,e_r$, every valid Hamiltonian tour must omit at least one of those arcs.

For a disjoint exhaustive branching rule, child $h$ forces $e_1,\dots ,e_{h-1}$ and forbids $e_h$, for $h=1,\dots ,r$. Every valid tour falls into the child indexed by the first omitted arc. Re-solve the corresponding assignment relaxations, prioritize small bounds, and repeat. Finitely many binary choices give an exact terminating search; its worst-case tree can be exponential. Assignment optima provide lower bounds, while complete tours provide upper bounds. Patching subtours or local improvement can improve the incumbent without changing the exact pruning argument.

Assume $n\ge 1$ and the integer coefficient bound $U\ge 1$. There are $m(n+1)$ integers to record. Each signed integer in $[-U,U]$ can be encoded in $\lceil {\log }_2(2U+1)\rceil$ bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is $\boxed{O(mn\log (U+1))}$. This is the bit-input model used for polynomial time; an arithmetic-operation count alone would not suffice.

We first construct a rational feasibility certificate for integer inequalities. Choose a feasible point and an orthant containing it, adding coordinate inequalities of the form $x_i\ge 0$ or $-x_i\ge 0$. The intersection $Q$ is nonempty. Starting at a point of $Q$, if the active constraint normals have rank less than $n$, choose a nonzero direction $d$ annihilating them. A sufficiently short move in either direction remains feasible, since every inactive constraint has positive slack. At least one direction has a finite endpoint: a nonzero coordinate of $d$ can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate $d$, so it is independent of the previously active normals. Their rank strictly increases. In at most $n$ moves we obtain a point with $n$ independent active constraints.

At that point $Bx=d_0$ for an invertible integer $n\times n$ matrix $B$. Its rows are original constraint rows or signed coordinate rows, and $d_0$ has entries from $b$ or zero. All entries have absolute value at most $U$. By Cramer's rule,where $B_i$ replaces column $i$ by $d_0$. The Hadamard determinant inequality bounds both determinants by $(\sqrt{n}U{)}^n\le (nU{)}^n$. The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by $R=(nU{)}^n$. The orthant argument is needed because $P$ itself may contain lines and have no vertex. If $U=0$ is allowed literally, all coefficients and right sides vanish, and $x=0$ is feasible; the printed fraction bound then needs $U$ replaced by $\max (1,U)$, since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.

Recording $n$ such fractions takes $O(n^2\log (nU))$ bits. A verifier checks that denominators are nonzero, changes their signs if needed, and verifies all inequalities by exact integer arithmetic after multiplying by positive denominators. The intermediate integers still have polynomial bit length. Thus a yes-instance has a polynomial-size, polynomial-time verifiable witness, and $\boxed{\mathrm{FP}\in \mathbf{NP}}$.

For optimization, let $c$ be rational with a finite binary encoding; clear its denominators to make it integer, which multiplies the objective by a positive constant and preserves its minimizers. All bit bounds below include the encoding length of $c$. Let $V=\max (1,{\max }_i|c_i|)$ and $B_0=nVR$.

A useful refinement of the preceding vertex argument is that if an objective is bounded below, a feasible point can be moved to an orthant vertex without increasing its objective. Choose the annihilating direction to have $c^{T}d\le 0$. If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If $c^{T}d=0$, choose either finite endpoint supplied by the orthant. Rank increases as before. There are only finitely many such vertices across the finitely many orthants. Every feasible point therefore has one of these vertices with no larger objective; taking the least vertex value proves that a finite optimum is attained at one of them.

The Cramer representations at this optimum have one common denominator $\det B$, of magnitude at most $R$. Therefore its objective value $z^{\ast }$ has a representation with denominator at most $R$ and numerator at most $B_0$. In particular $|z^{\ast }|\le B_0$. No enumeration of orthants or vertices is part of the algorithm; they provide only polynomial-bit bounds.

Here is an exact linear optimization from a feasibility oracle. First call the assumed ellipsoid method feasibility routine on $P$; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality $c^{T}x\le -B_0-1$. A yes answer proves unboundedness below, because any finite optimum would be at least $-B_0$; an unbounded objective necessarily gives a yes answer. Thus the infeasible, unbounded and finite-optimum cases are distinguished using two feasibility calls.

In the finite case, maintain an infeasible lower threshold $-B_0-1$ and a feasible upper threshold $B_0$. Bisect the interval, querying $c^{T}x\le t$ each time. After polynomially many calls its length is less than $1/(2R^2)$, and $z^{\ast }$ lies in the resulting interval. Distinct reduced fractions with positive denominators at most $R$ differ by at least $1/R^2$, so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint $t$, $|z^{\ast }-t|<1/(4R^2)\le 1/(2q^2)$, where $q\le R$ is the denominator of $z^{\ast }$. Thus $z^{\ast }$ occurs among the continued-fraction convergents of $t$. Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most $R$ in the interval. If $t=z^{\ast }$, use the final exact convergent. The Euclidean algorithm and all thresholds have polynomial bit length.

Even if the feasibility routine returns only a decision, an optimal point can be recovered without assuming a witness-producing oracle. Add $c^{T}x=z^{\ast }$ and $-R\le x_i\le R$ for all $i$. This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of $z^{\ast }$ and setAll vertex coordinates of this fixed convex polytope have denominators at most $D_0$ by the same determinant argument. Minimize $x_1$, recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for $x_2$, and so on. Each restriction is an optimal face of the same original bounded convex polytope, so its vertices are original vertices. The single denominator bound $D_0$ therefore works at every step; repeated new precision bounds do not grow exponentially. After $n$ steps all coordinates are fixed to a feasible optimizer. There are polynomially many calls on polynomial-length rational instances, converted to integer inequalities by clearing denominators. Consequently linear optimization has a polynomial-time algorithm whenever linear feasibility does, with exact optimal value and optimizer, and correct reports of infeasibility or unboundedness.

The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

Use a complete directed graph on $n\ge 3$ cities, with integral arc costs $c_{ij}$ and a threshold $L$. A symmetric cost matrix also represents the undirected travelling salesman problem by orienting a tour. Let the binary variable $x_{ij}$ indicate that city $j$ follows city $i$, and forbid self-arcs. The decision integer programming formulation asks whether the following system has a solution:The in-degree and out-degree equations make the selected arcs a cycle cover of a directed graph. Any proper graph cycle on a city set $S$ would violate its subset inequality, so the selected arcs form one Hamiltonian cycle. Conversely, a Hamiltonian cycle obeys every inequality: a proper subset cannot contain all the successor arcs of its graph vertices. Thus the binary feasibility system is equivalent to the decision travelling salesman problem. The subset formulation has exponentially many inequalities, which is harmless for this formulation; verifying a proposed tour does not require listing them.

To call this decision problem NP-complete means two separate things. It belongs to NP: a yes-instance has a polynomial-length certificate in computational complexity, namely the cyclic ordering of the cities, and a deterministic algorithm checks distinct visits, the return to the start, and the total cost in polynomial time in the binary input length. It is also NP-hard: every decision problem in NP has a polynomial-time many-one reduction to it, preserving yes and no answers. This is a statement about worst-case computation on finite encodings, not a proof that every individual tour is hard to find or that no polynomial algorithm exists; that last conclusion would require $\mathrm{P}\ne \mathrm{NP}$.

For the strict-threshold decision Max-TSP, choose an integer $M\ge {\max }_{i\ne j}{c}_{ij}$ and replace each arc cost by $c_{ij}^{\prime }=M-c_{ij}\ge 0$. Every tour uses exactly $n$ arcs, soSet the new threshold to $L^{\prime }=nM-L-1$. Its encoding length, the transformed matrix's encoding length and the computation time are all polynomial in the original input length. If thresholds are required to be nonnegative, take $M\ge \max (0,\max c_{ij},L+1)$; the same identity works. Symmetry of costs is preserved. This is a polynomial-time many-one reduction from decision travelling salesman problem to decision Max-TSP, so the latter is NP-hard. A tour is again a polynomially verifiable certificate in computational complexity, now checking strict excess over $L^{\prime }$, soFor the approximation algorithm, use the standard nonnegative-length setting on a complete graph; no triangle inequality is required. Solve the maximum-weight assignment problem with diagonal assignments forbidden, for example by applying the Hungarian algorithm to the negative weights. The resulting cycle cover of a directed graph has weight $W$ with $W\ge \mathrm{OPT}$, since every tour is an allowed assignment.

If it already has a single graph cycle, it is an optimal tour. Otherwise remove a least-weight arc from each graph cycle. A graph cycle of $r\ge 2$ arcs and weight $W_r\ge 0$ loses at most $W_r/r\le W_r/2$. The remaining arcs form vertex-disjoint graph paths covering all cities. Join the endpoint of each graph path to the start of the next, cyclically. The required arcs exist by completeness, and their nonnegative weights cannot diminish the retained weight. The resulting single Hamiltonian cycle therefore satisfiesThe Hungarian algorithm takes $O(n^3)$ arithmetic operations, and finding the graph cycles, cutting them and patching the graph paths takes $O(n)$ further operations. For rational or integer weights these operations have polynomial encoding length, giving polynomial time. With symmetric costs, the same directed construction is a valid undirected tour after forgetting its orientation. This is the cycle-cover patching half-approximation for Max-TSP.

Nonnegativity is essential to this multiplicative guarantee. If arbitrary signed weights were allowed, giving every arc cost $-1$ would make every tour have weight $-n$, while half the optimum is $-n/2$. No tour could achieve the requested bound. Thus “length” has its usual nonnegative meaning in the approximation assertion.

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 chain of $r$ diamond-shaped graph stages has $3r+1$ vertices and $4r$ edges, but $2^r$ distinct source-to-target paths: at each stage choose either of two branches. Each path has its own inequality. Therefore the number of displayed path constraints is not polynomially bounded in the graph size. Redundancy among some inequalities would not change this count of the given formulation.

The positive integer edge costs imply, for any feasible point,Thus the feasible set lies in the Euclidean ball of radius $100$ centered at zero. That ball lies inside $[-100,100{]}^m$, so its volume is at most $200^m$. This proves the requested $O(200^m)$ enclosing-volume bound, and provides an initial ellipsoid, for example with center zero and shape matrix $10^{4}I$.

The ellipsoid method needs a separation oracle, rather than an explicit list of every constraint. For a proposed center $z$, first scan the coordinates and the budget inequality. If some $z_e<0$, some $z_e>1$, or ${\sum }_e{c}_e{z}_e>k$, return the corresponding violated inequality as the separating half-space. These tests take $O(m)$ arithmetic operations.

Once those tests pass, assign nonnegative edge length $z_e$ to every edge and solve the shortest path problem from $s$ to $t$. The Dijkstra algorithm finds a minimum-length path and stores its predecessors in polynomial time. If its length is less than one, returnfor the minimizing path $p$. This inequality contains every feasible point and is violated by $z$. If the shortest length is at least one, every path constraint holds; if no path exists, those constraints are vacuous. In either case $z$ is feasible. This is path-constraint separation by shortest paths; checking a single shortest path replaces checking exponentially many paths.

The rational ellipsoid method feasibility theorem now gives polynomial running time in the dimension and coefficient encoding bounds when the oracle runs in polynomial time. Here every path row has coefficients zero or one, and all other coefficients and right sides are bounded integers. Although there are exponentially many rows, their individual encoding lengths are polynomial in $m$. The containing-radius bound and the rational precision bounds are also polynomially describable. For a simple graph $m=O(n^2)$, this gives a worst-case running time polynomial in $n$; in general the natural bound is polynomial in the encoded graph size $n+m$.

Use the exact rational feasibility version of the ellipsoid method, which handles lower-dimensional polyhedra by rational precision bounds or an appropriate relaxation. Nonemptiness must not be inferred from a positive-volume argument: this feasible set can have empty interior. The allowed algorithmic theorem supplies that detail, while the explicit shortest-path oracle supplies the crucial efficient separation.

The supplied hint interchanges its item and bidder indices in the first-value identity. If the first greedy choice assigns item $n$ to bidder $m$, the correct quantity is $w=v_m(\{n\})$, and the identity isIndeed, the eventual bundle of bidder $m$ has the form $S_m^{\prime }\cup \{n\}$, whose value is $w+v_m^{\prime }(S_m^{\prime })$; the other bidders' values are unchanged. Every later marginal contribution for bidder $m$ is exactly its marginal in the residual problem, and this is also true for every other bidder. Thus the remainder of the greedy run is the greedy run on $v^{\prime }$, with the same tie choices. The residual values are nonnegative and increasing; they remain submodular set functions as allowed in the question.

We prove the greedy half-approximation for submodular welfare by induction on the number of items. The zero-item case has $A(v)=\mathrm{Opt}(v)={\sum }_i{v}_i(\varnothing )\ge 0$, so the claimed inequality holds. This base case also handles the fact that the question does not explicitly normalize empty-bundle values to zero.

For the induction step, letbe the first greedy marginal. Since the choice maximizes all available marginals,Take an optimal allocation and let $i$ be the owner of item $n$. If $i\ne m$, remove that item from $i$'s bundle and give it to $m$. By submodularity, the loss to its old owner isMonotonicity makes the recipient's gain nonnegative. The modified allocation, now with $n$ assigned to $m$, therefore has value at least $\mathrm{Opt}(v)-\delta$. If $i=m$, no modification is necessary and this bound still holds. Removing $n$ and translating bidder $m$'s value by $w$ produces a feasible residual allocation, soInduction applied to that residual problem now givesThus the greedy algorithm is a one-half approximation. Empty-bundle constants cause no difficulty because all are nonnegative and $\delta \le w$.

At each of $n$ stages evaluate the marginal for at most $m$ bidders and $n$ remaining items. This requires $O(m{n}^2)$ value queries, and polynomial additional work with bundle bit-vectors and cached current values. Hence it is a polynomial time approximation algorithm in the value-oracle model, assuming polynomial time bid evaluations. If every bundle bid is explicitly listed, this query bound is polynomial in that larger explicit input as well. The exponentially many possible bundles do not require enumerating allocations.

The PDF's small superscript is essential: $f(x)=a^x\mathrm{mod}N$. Interpret $r$ as the least positive period, the multiplicative order of $a$ modulo $N$. If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, $a=1,N=8$ gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, $a^r\equiv 1(\mathrm{mod}N)$, so $a$ is a unit. ThusIn particular, different residue classes modulo $r$ have different function values, which is necessary for the usual quantum period finding coset argument.

Prepare $N^{-1/2}{\sum }_x|x⟩|1⟩$ by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute $a^{2^j}\mathrm{mod}N$, then multiply the value register by that known number controlled on bit $j$ of $x$. These controlled modular multiplications are reversible because $a$ is a unit; their inverses use the modular inverses of the same constants. This produces $N^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}N⟩$ with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.

Measure the value register. Since $r\mid N$, its fiber is exactly one coset, and the first register becomesThe quantum Fourier transform of a periodic coset state is supported uniformly on the $r$ outcomes $c=jN/r$, $0\le j<r$. Indeed the inner geometric series ${\sum }_{\ell =0}^{N/r-1}{e}^{2\pi i\ell rc/N}$ is zero unless $(N/r)\mid c$, and each allowed amplitude has modulus $1/\sqrt{r}$.

Take two independent Fourier samples $c_1,c_2$ and returnThis is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of $r$. For each such prime $\ell$, both $j_1$ and $j_2$ are divisible by $\ell$ with probability ${\ell }^{-2}$. ThereforeThe number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and $\zeta (2)={\pi }^2/6$. The candidate can also be certified by $a^{\hat{r}}\equiv 1(\mathrm{mod}N)$: it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in $\log N$. Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least $6/{\pi }^2$ in polynomial time.

The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete under polynomial-time many-one reductions. Membership in NP follows by guessing an assignment and evaluating the formula in time polynomial in its description length.

For hardness, let $L\in \mathrm{NP}$ have a deterministic polynomial-time verifier $M(x,y)$, with a polynomial witness-length bound. Use a fixed polynomial certificate length: a short certificate is encoded by its length followed by padded data, and the verifier checks this encoding. Pad the computation to exactly $T=T(|x|)$ steps, with accepting and rejecting states absorbing. Enlarge $T$ polynomially if necessary to cover input/witness initialization. A standard polynomial slowdown permits a single-tape Turing machine, so it suffices to handle that model.

Encode a tape cell by a fixed number of bits recording its alphabet symbol and either no head or the head's finite control state. Starting with one head, a cell's next label depends only on its own label and the two neighboring labels: a head can change the symbol where it sits and can enter only a neighbor. Each such finite local function has a constant-size Boolean circuit. The initial row fixes $x$, blanks and the starting head, leaving only the witness bits as Boolean circuit inputs. There are $O(T)$ relevant cells with blank margins beyond every possible head position, and $T$ updates. Repeating these local Boolean circuits produces a Boolean circuit $C_x(y)$ of size $O(T^2)$, with an output detecting an accepting head in the final row. The construction is computable in polynomial time. Induction on rows shows that every assignment to $y$ produces exactly the verifier's valid computation; invalid local encodings can be assigned arbitrary Boolean circuit behavior because they never arise from the valid initial row.

Convert this Boolean circuit to conjunctive normal form using a Tseitin transformation. Introduce one variable for each wire, and encode each gate output $z$ by:

Unit clauses fix constant sources and assert the final output. Each input assignment has exactly one extension to its gate values, so the resulting formula $F_x$ is satisfiable precisely when some witness makes $M(x,y)$ accept. It has $O(T^2)$ clauses of bounded length and is produced in polynomial time. ThusThis proof also gives hardness for clauses of at most three literals, without needing a separate satisfiability assumption.

A proposed assignment for 2UN-SAT can be checked in polynomial time, including checking the syntactic restriction, so the language belongs to NP.

For an explicit reduction, parse any Boolean formula into a Boolean circuit over binary AND (logical conjunction), binary OR (logical disjunction) and unary NOT (negation), and apply the gate equivalences in part (a), asserting its output. Every gate clause has at most two positive literals: the AND clauses have respectively one, one and one; the OR clauses have one, one and two; and the NOT clauses have two and zero. The unit output/constant clauses also obey the restriction. Hence the resulting formula is an instance of 2UN-SAT.

The Tseitin transformation is linear in the gate description, and its auxiliary variables enforce the gate values rather than relaxing their relation to the inputs. Therefore the original formula is satisfiable if and only if the transformed restricted formula is satisfiable. This is a polynomial-time many-one reduction from SAT, whose hardness follows from the Cook-Levin theorem. ConsequentlyThe condition limits positive literals, without limiting total clause length.

The AND-NOT circuit value problem belongs to P: validate the Boolean circuit and evaluate its gates in a topological ordering. Evaluation takes polynomial time even if its description is not already in a topological ordering.

For P-completeness we use logspace many-one reductions. Start from the supplied circuit value problem over the usual AND (logical conjunction), OR (logical disjunction) and NOT (negation) basis. Retain AND and NOT gates, and replace every OR gate by the De Morgan's laws gadgetThis adds only a constant number of gates per old gate, preserves its truth value for all inputs and keeps the Boolean circuit acyclic. If the format includes constant source nodes, replace them by additional input nodes assigned fixed bits zero and one; these are inputs, not disallowed gates. Larger fan-in gates can first be replaced by binary trees of their inputs.

To output the new description, keep the old gate index and a constant-size gadget position, rescan old references when necessary, and assign consistent new indices to each gadget's terminal output. These counters and references occupy $O(\log |C|)$ bits; the input assignment is copied with any constant-source bits appended. Thus the construction is a logspace many-one reduction preserving acceptance. Since Boolean circuit Value is P-complete under such reductions,

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

Write $Q=2^n$, $t=(p-1)(q-1)$ and $a=t/Q$. The easy starting state is uniform over all $n$-bit labels, so its good fraction is $a$, not $t/N$. For distinct primes one has $a\ge 1/4$. If both primes are odd, $t/N\ge (1-1/3)(1-1/5)=8/15$ and $N/Q\ge 1/2$, giving $a\ge 4/15$. If one prime is two, the other is an odd prime $q$; since $2q$ has $n$ bits, $q>2^{n-2}$, and $t=q-1\ge 2^{n-2}=Q/4$.

The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by $|k⟩|1⟩$ with $1\le k<N$ and $\gcd (k,N)=1$. Its squared overlap with $|\Psi ⟩$ is exactly $a\lambda =1/4$. The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements $S_G=I-2{\Pi }_G$.

The starting-state reflection $D_{\Psi }=2|\Psi ⟩⟨\Psi |-I$ uses the inverse of its known preparation and a reflection on the all-zero state. Applying $D_{\Psi }{S}_G$ once invokes exact amplitude amplification at $\theta =\pi /6$, and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes $N$, that label is not coprime to itself, so the predicate $k<N$ is equivalent and avoids admitting labels outside the intended range.

The supplied $p,q$ determine $t$ in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in $n$ in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes $\sqrt{\lambda },\sqrt{1-\lambda }$; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra $|1⟩$ can be reset by a Pauli X gate.

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.