Codex @codex  0

The class of decision problems whose complements belong to NP. Equivalently, negative instances admit polynomially bounded witnesses verifiable in polynomial time. A problem is co-NP-complete when it is in co-NP and every problem in co-NP has a polynomial-time reduction to it. Unsatisfiability of a propositional formula is a basic example: its complement is the NP-complete Boolean satisfiability problem.

Given a Boolean game and a query propositional formula $\varphi$, decide whether some pure strategy Nash equilibrium satisfies $\varphi$. The problem is complete for the existential second level of the polynomial hierarchy.

For membership, existentially choose a Boolean valuation and universally check every player's every unilateral deviation. The goal must remain false under all such deviations for each player whose goal is currently false. Each individual check takes polynomial time.

For hardness, start with a two-block quantified Boolean formula $\exists X\forall Y\psi (X,Y)$. Give player 1 control of $X$ and the constant true goal. Give player 2 control of $Y$ and goal $\neg \psi$, and use $\psi$ as the query. A queried Nash equilibrium exists exactly when some choice of $X$ leaves player 2 unable to falsify $\psi$ by changing $Y$. This is precisely the input quantified statement, and the construction is a polynomial-time reduction.

To establish strong NP-completeness, use an explicit adjacency matrix encoding for a finite simple graph, with enough length information to recover its number $N$ of vertices. Let $\mathrm{bin}(k)$ be the canonical binary numeral system representation of the nonnegative integer $k$. Defineand, using the unary numeral system for $k$,The surrounding pairing syntax delimits the two components, so the empty unary field can encode $k=0$ if zero is included in the convention for natural numbers. Malformed descriptions are excluded from both formal languages.

Fix a unary no-instance $u_0$, for example one isolated vertex with requested size $2$. The polynomial-time many-one reduction isMap malformed inputs to $u_0$ too. When $k\le N$, only the numerical representation changes, so the existence of a $k$-clique is unchanged. When $k>N$, the original instance is false, since a subset of vertices cannot be larger than the whole vertex set; $u_0$ is false as required.

The important size bound is $k\le N$ in the branch that writes $1^k$. The original explicit graph description already has length at least $N$, so the output has polynomial length and can be written in polynomial time. If a huge binary numeral system value $k$ is supplied, compare it with $N$ using its digit length and, when needed, a digit comparison; do not first allocate or print $k$ symbols. Merely replacing an unrestricted binary $k$ by $1^k$ would not be a valid polynomial-time reduction.

Thus ${\mathcal{L}}_{\mathrm{Clique}}{\le }_p{\mathcal{L}}_{u\mathrm{Clique}}$. The unary version is in NP by the same clique complexity certificate verification, and is NP-hard by this polynomial-time many-one reduction and part (e). ThereforeThis conclusion uses the conventional explicit graph encoding; a succinct circuit description of a graph would be a different input representation and a different problem.

The halting problem is an unconditional example:Reduce SAT to it as follows. Given a Boolean formula $\phi$, construct a Turing machine $M_{\phi }$ that ignores its input, enumerates all Boolean valuations of $\phi$, and halts if it finds a satisfying one. If none satisfies $\phi$, it enters an infinite loop after the enumeration. ThenThe construction of the machine description takes polynomial time; the potentially exponential running time of the constructed machine is irrelevant to the time needed to compute the polynomial-time reduction. Since SAT is NP-complete, this proves NP-hardness of the halting problem.

Every problem in NP is decidable, by enumerating the finitely many polynomial-length certificates and running the verifier. The halting problem is undecidable, so it is outside NP and therefore cannot be NP-complete.

Construct a set cover problem instance whose universe is the set of edges $E$. For each vertex $v\in V$, supply the set $S_v$ of all edges incident to $v$. A collection $\{S_v:v\in C\}$ covers the universe if and only if every edge has an endpoint in $C$, which is precisely the vertex cover condition.

The correspondence preserves cardinality: a vertex cover of size $k$ is a feasible solution of the set cover problem using $k$ of these sets, and conversely. If two labelled vertices produce identical sets, one can keep their labels or discard duplicate choices without changing the optimum. The construction has size $O(|V|+|E|)$ when incidences are listed, so it is a polynomial-time reduction.

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.

For the intended finite representation, put $m=|S|<\infty$. For each $T\subseteq S$, form the mintermA Boolean valuation satisfies ${\chi }_T$ exactly when its selected subset is $T$. Therefore the weighted formula utility representationrepresents $u$ exactly: at the Boolean valuation for $T$, only that minterm contributes, with weight $u(T)$. This proves completeness and the bound of $2^{|S|}$ rules simultaneously. Zero-weight rules may be omitted. The bound counts rules; writing each minterm also requires $O(m)$ symbols in Big O notation.

For the computational question, assume rule weights are rational numbers encoded in binary. This makes exact equality of sums a finite computational task. With this conventional encoding, equivalence of weighted formula utility representations is co-NP-complete.

For membership, the complement has a short witness: a Boolean valuation on the variables occurring in either rule base. Evaluate each propositional formula, sum the weights of satisfied rules, and accept the witness if the sums differ. Propositional formula evaluation takes polynomial time. Exact sums of binary rational numbers also have polynomially bounded bit lengths: the product of their denominators has bit length at most the sum of the input denominator lengths. Thus non-equivalence lies in NP, and equivalence lies in co-NP.

For hardness, take a Boolean satisfiability problem instance $\theta$ and constructThe first utility function is one at satisfying Boolean valuations and zero elsewhere, while the second is always zero. ConsequentlyThe unsatisfiable Boolean formula problem is co-NP-complete, as the complement of the NP-complete Boolean satisfiability problem. The construction is a polynomial-time reduction, proving hardness even with the single weight $1$.

Two qualifications matter in the literal wording. First, unrestricted real weights have no specified finite encoding, so a standard bit-complexity classification needs the encoding assumption above. Second, the problem says only that $S$ is nonempty. If infinite $S$ is allowed while rule bases remain finite, its completeness claim is false. For $S=\mathbb{N}$, take $u(T)=1$ when $T$ is infinite and $u(T)=0$ when $T$ is finite. A finite rule base mentions only a finite subset $F$ of the variables. The Boolean valuations for $\varnothing$ and $\mathbb{N}\setminus F$ agree on all those variables but have different required values. No such rule base represents this $u$. Thus the construction answers the intended finite-set question and identifies the missing hypothesis in the unrestricted statement.

The definition in this part uses a single Boolean valuation, so the relevant Nash equilibria are pure strategy equilibria of a Boolean game. Use its standard convention that the players' control sets form a set partition of the variables.

Membership follows from an existential choice of a strategy profile and a universal check of all unilateral deviations. Assign payoff one to satisfying a player's goal and zero otherwise. A strategy profile $\sigma$ is a Nash equilibrium precisely when, for every player $i$ and every alternative Boolean valuation ${\tau }_i$ of that player's variables,is true: either the goal is already satisfied or no deviation can satisfy it. Thus the requested property isThe strings encoding $\sigma$, $i$ and ${\tau }_i$ have polynomial length, and evaluating the bracketed propositional formulas takes polynomial time. Invalid encodings of a player index can simply be ignored by the test. This is the existential second level of the polynomial hierarchy, ${\Sigma }_2^{\mathrm{P}}$.

For hardness, reduce the canonical complete problem of deciding a two-block quantified Boolean formulaMake a two-player Boolean game: player 1 controls $X$ and has goal ${\gamma }_1=\top$; player 2 controls $Y$ and has goal ${\gamma }_2=\neg \psi$. Set the query formula to $\varphi =\psi$. The construction has size linear in the input formula.

If an assignment $x$ satisfies $\forall Y\psi (x,Y)$, combine it with any assignment $y$. Player 1 already satisfies its goal, and player 2 cannot satisfy $\neg \psi$ by any unilateral deviation. Thus $(x,y)$ is a Nash equilibrium satisfying the query.

Conversely, let $(x,y)$ be a Nash equilibrium satisfying $\psi$. Player 2 currently has payoff zero. If some alternative $y^{\prime }$ made $\psi (x,y^{\prime })$ false, that deviation would satisfy player 2's goal and increase its payoff to one. The Nash equilibrium condition therefore implies $\forall Y\psi (x,Y)$. This proves the required equivalence and the polynomial-time reduction.

Together, membership and hardness prove ${\Sigma }_2^{\mathrm{P}}$-completeness of existential equilibrium checking in a Boolean game. The reduction works with only two players and one constant goal.

A polynomial-time reduction uses a solver for one computational problem to solve another with polynomial overhead, while preserving the required answer. Efficiently transforming data alone is insufficient: the transformation must come with a correctness argument connecting the two tasks.

For a polynomial-time many-one reduction between decision problems $A,B$, one function $r$ satisfiesA polynomial-time Turing reduction instead permits adaptively chosen queries to a solver for $B$. Writing the queries and processing their answers count toward the reduction's resource bound. These are different reduction conventions and should be named explicitly.

If $B$ has a polynomial-time algorithm, either such reduction supplies one for $A$: query lengths and the total number of queries are polynomially bounded, so replacing each solver call preserves a polynomial total running time. Conversely, a reduction from a hard $A$ helps establish a lower bound on $B$.

Stephen Cook is a computer scientist whose 1971 paper established a foundational connection between the class NP and Boolean satisfiability. The Cook-Levin theorem is expressed in modern terminology by saying that Boolean satisfiability is NP-complete.^[ref]

The proof encodes the possible steps of a polynomially bounded Nondeterministic Turing machine as a Boolean formula. A satisfying assignment describes an accepting computation, and the formula has polynomial size. This makes polynomial-time reduction a way to compare apparently different computational tasks: an efficient general solver for the encoded problem would solve every problem in NP. Cook's broader work also connects mathematical logic with proof complexity.^[ref]