Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 2

Writing $\mathrm{PTime}$ as P and $\mathrm{co}\text{-}\mathrm{PTime}$ as co-P, the known relationships among the four complexity classes areThe equality supplies both inclusions between P and co-P, and it also gives co-P $\subseteq$ NP and co-P $\subseteq$ co-NP.

For the equality, a deterministic polynomial-time algorithm halts on every input; interchange its accepting and rejecting outcomes to decide the complement of a set in the same polynomial time. For P $\subseteq$ NP, a Nondeterministic Turing machine can simply make no choices and follow the deterministic computation. Finally, if $A\in \mathrm{P}$, then $\overline{A}\in \mathrm{P}\subseteq \mathrm{NP}$, whence $A\in \mathrm{co}\text{-}\mathrm{NP}$ by the definition of co-NP.

Neither NP $\subseteq$ co-NP nor co-NP $\subseteq$ NP is known; either would imply equality by taking complements. Nor is either inclusion of P into NP or co-NP known to be strict. These unresolved relationships must not be presented as strict separations.

The linear speedup theorem concerns multitape Turing machines whose finite control and tape alphabet may change. Formally, for $k>1$, if a deterministic $k$-tape Turing machine decides $A$ within $T(n)$ steps on every input of length $n$, then for every constant $c>0$ there is a deterministic $k$-tape Turing machine deciding the same formal language withThe additive constant is independent of $n$; in the usual normalized formulation the bound is $T(n)/c+n+2$, with the integer-rounding convention absorbed in the constant.^[ref]

The construction packs a fixed number of old tape symbols into each new symbol and uses a larger finite control to simulate blocks of old steps. Initial input packing explains the additive linear term. If $T(n)/n\to \infty$, choosing a larger constant $c$ makes the total asymptotic time complexity an arbitrarily small constant multiple of $T(n)$.

It does not promise arbitrary speed increases on fixed hardware. Larger packed symbols and transition tables cease to be single constant-cost hardware operations without limit. The theorem also retains the input-reading overhead. It is a statement about changing the abstract machine description and primitive operations, rather than an unlimited implementation optimization on one processor.

Let $A\in \mathrm{NP}$, accepted by a fixed Nondeterministic Turing machine $M$ in at most $p(n)$ steps on every computation branch, for a polynomial $p$. Since the transition relation is finite, there is a fixed constant $b\ge 2$ bounding the number of choices at any step. Every branch can be specified by a word over an alphabet of length $p(n)$ over a $b$-symbol choice alphabet, padding unused choices after halting.

A deterministic Turing machine enumerates all $b^{p(n)}$ such choice sequences and simulates the corresponding branches for at most $p(n)$ steps each. It accepts if some simulation accepts, and rejects after all have failed. Every possible accepting branch is included, and the time cutoff guarantees termination even on invalid choice sequences. A standard direct simulation has only polynomial overhead per branch, givingfor a suitable polynomial $q$. This is a deterministic exponential time bound. ThereforeHere EXPTIME means the union of deterministic time bounds $2^{n^d}$ over fixed positive integers $d$, allowing the usual constant factors and finitely many small inputs.

Entail is co-NP-complete under polynomial-time many-one reductions. For valid propositional formulas, semantic entailment holds exactly when the logical conjunction of the premise and the conclusion's logical negation is an unsatisfiable Boolean formula:A counterexample to semantic entailment is a Boolean valuation making $\phi$ true and $\psi$ false. Guessing one bit for each distinct Boolean variable and evaluating both propositional formulas is a polynomial-time algorithm. Thus the complement of Entail belongs to NP. Malformed descriptions, also in that complement, can be accepted after a deterministic syntax check. Hence Entail belongs to co-NP as a formal language over all strings.

For hardness, the unsatisfiable Boolean formula problem is co-NP-hard: if $A\in \mathrm{co}\text{-}\mathrm{NP}$, then $\overline{A}\in \mathrm{NP}$, and the permitted NP-hardness of SAT supplies a polynomial-time many-one reduction $r$ withWe may ensure $r(x)$ is always a valid propositional formula, replacing any malformed output by a fixed contradiction. It follows that $x\in A$ exactly when $r(x)$ is unsatisfiable. This justifies using the unsatisfiability problem as a hardness source without an extra assumption.

Map a valid propositional formula $\theta$ towhere $p$ is a fixed Boolean variable. The second propositional formula is false under every Boolean valuation. Consequently it is entailed by $\theta$ precisely when no Boolean valuation satisfies $\theta$. ThusThe output has only constant additional length and is computable in polynomial time. If the source unsatisfiability language rejects malformed strings, map them to the fixed no-instance $⟨p,p\wedge \neg p⟩$. This completes a total polynomial-time many-one reduction and proves the claimed co-NP-completeness.

The clique decision problem belongs to NP. First reject $k>|V(G)|$. Otherwise a complexity certificate lists $k$ distinct vertices. Check distinctness and test that each of the $\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ pairs is an edge. Under a conventional explicit graph encoding, the complexity certificate length and verification time complexity are polynomial in the input length. The early rejection is relevant when $k$ is given in the binary numeral system.

For NP-hardness, first transform a SAT instance into an equisatisfiable conjunctive normal form $F=C_1\wedge \cdots \wedge C_m$ of polynomial size using a Tseitin transformation. This step avoids the possibly exponential increase caused by distributing arbitrary Boolean formulas into conjunctive normal form. Introduce a fresh Boolean variable for each subformula, constrain it to have the connective's truth value using a constant number of Boolean clauses, and require the top variable to be true. A Boolean valuation of the original Boolean variables satisfies the original Boolean formula exactly when it extends to a satisfying assignment of these constraints.

Create one vertex for each occurrence of a Boolean literal in each Boolean clause. Join two such vertices by an edge exactly when they belong to different Boolean clauses and their Boolean literals are not a variable and its logical negation. Set $k=m$. There are at most as many vertices as Boolean literal occurrences and at most quadratically many edges, so this construction takes polynomial time.

If $F$ has a satisfying assignment, choose one true Boolean literal occurrence from each Boolean clause. No two selected Boolean literals are contradictory, so their $m$ vertices form a clique. Conversely, an $m$-clique contains at most one vertex from each Boolean clause, because there are no edges within a Boolean clause. It therefore selects exactly one occurrence from each of the $m$ Boolean clauses. The selected Boolean literals are pairwise noncontradictory, so assign their Boolean variables the indicated truth values and assign any other Boolean variables arbitrarily. This Boolean valuation satisfies every Boolean clause.

An empty Boolean clause gives no vertex in its group, correctly preventing an $m$-clique. An empty logical conjunction can instead be mapped to a fixed yes-instance, avoiding any convention about $k=0$. Malformed SAT descriptions can be mapped to a fixed no-instance. We have proved

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.