TCS: What If P = NP?

What If P = NP?

From Decision to Search

Suppose SAT has a polynomial-time decision algorithm. We can recover a satisfying assignment through a sequence of decision queries

The invariant is that the currently restricted formula remains satisfiable. There are at most $n+1$ decision queries for $n$ variables, and each restricted instance has polynomial size

Searching for Arbitrary NP Witnesses

For a polynomial-time verifier $V$ and a candidate witness prefix $u$, define the prefix-extension question

$$E(x,u)=1 \quad\Longleftrightarrow\quad \exists v:\ V(x,uv)=1$$

Use a fixed polynomial witness length, padding shorter witnesses through the verifier’s encoding if needed. The extension problem is in $\mathrm{NP}$, since $v$ is a polynomial-length certificate

The prefix problem need not be identical to the original decision language. The general argument uses the assumption that all NP languages are in $\mathrm P$

Optimization and Applications

Binary Search on a Threshold

Suppose feasible solutions have polynomial-length encodings, feasibility is efficiently checked, and the objective has a polynomial-time computable integer value of polynomial bit length

For maximization, ask

$$\exists y:\ V(x,y)=1\land\operatorname{value}(x,y)\ge k$$

This is an NP question. Binary search over the objective range uses polynomially many queries even when the range contains exponentially many integers, because its endpoints have polynomial bit length

After finding the optimum threshold, witness search recovers an optimal solution. This applies to problems such as maximum cut and longest simple path

Learning and Cryptography

For a finite hypothesis representation $h_\theta$ with polynomially many parameter bits and efficient evaluation, the question of whether some $\theta$ makes at most $k$ errors on a given sample is in $\mathrm{NP}$

Under $\mathrm P=\mathrm{NP}$, the minimum empirical error and a parameter vector achieving it can therefore be found efficiently. Generalization to unseen examples still depends on the hypothesis class and the data distribution

A candidate preimage of an efficiently computable function is also efficiently verifiable. If $\mathrm P=\mathrm{NP}$, a preimage of a function value can be found by witness search, ruling out one-way functions in the usual computational sense

Likewise, when a secret key or equivalent explanation has polynomial length and can be checked against available data, finding one becomes an NP search task. Information-theoretic secrecy, such as a correctly used one-time pad, is governed by a different condition

Searching for Short Proofs

Let $V(\varphi,\pi)$ be a polynomial-time checker for a fixed formal proof system. Consider

$$\operatorname{SHORTPROOF} =\{\langle\varphi,1^m\rangle: \exists\pi,\ |\pi|\le m,\ V(\varphi,\pi)=1\}$$

The unary bound $1^m$ makes the candidate proof polynomial in the total input length. Thus this bounded proof-existence problem lies in $\mathrm{NP}$

If $\mathrm P=\mathrm{NP}$, a proof can be found in time polynomial in $|\varphi|+m$ whenever one of length at most $m$ exists

The bound is essential. A true statement may have no proof in the chosen system, or its shortest proof may be enormous. Efficient bounded proof search is compatible with incompleteness

Quantifier Alternation

NP uses one existential block over a polynomial-time predicate. More blocks give the polynomial hierarchy

Assume $\mathrm P=\mathrm{NP}$. For fixed $(x,y)$, the negation of $\forall z:R(x,y,z)=1$ is the NP question $\exists z:R(x,y,z)=0$. Its answer can be computed in polynomial time and complemented

The remaining outer existential question is then another NP problem, also decidable in polynomial time. Repeating this argument for any fixed number of blocks gives

$$\mathrm P=\mathrm{NP}\quad\Longrightarrow\quad\mathrm{PH}=\mathrm P$$

The number of blocks must be a fixed constant for this argument. An input may encode polynomially many alternating quantifiers in TQBF, which leads to the space complexity of the next lecture

Counting Is a Further Task

Given a circuit $C$, define its number of satisfying inputs by

$$\#C=|\{x\in\{0,1\}^n:C(x)=1\}|$$

Counting accepting witnesses defines the function class $\#\mathrm P$. Knowing whether the count is zero does not directly determine its exact value

Stockmeyer’s approximate-counting theorem provides randomized multiplicative approximation with an NP oracle. Hashing helps estimate the size of the witness set through existence queries

If $\mathrm P=\mathrm{NP}$, those oracle queries become polynomial-time computations. Exact counting does not follow from the decision-to-search argument; an additional theorem would be needed to conclude that every $\#\mathrm P$ function is polynomial-time computable

Oracle Machines and Relativization

An oracle machine can query membership in a fixed language $A$. One oracle answer costs one step, while writing the query string still takes time

The resulting classes are denoted by $\mathrm P^A$ and $\mathrm{NP}^A$. For example,

$$\mathrm{NP}\cup\mathrm{coNP}\subseteq\mathrm P^{\operatorname{SAT}}$$

A relativizing argument continues to work when the same arbitrary oracle is supplied to all the machines involved

An Oracle That Separates P and NP

For an oracle $A$, define

$$L_A=\{1^n:\exists w\in\{0,1\}^n,\ w\in A\}$$

This language is in $\mathrm{NP}^A$: guess one length-$n$ string and ask the oracle

Enumerate clocked deterministic polynomial-time oracle machines $M_1,M_2,\ldots$. At stage $i$, choose a fresh length $n$ larger than every string length fixed earlier and with $2^n$ larger than the running-time bound of $M_i$ on $1^n$

Simulate $M_i$ while preserving previous oracle answers and answering every new query negatively. Freeze every answer made during this simulation

• If $M_i$ accepts, put no length-$n$ string in $A$
• If $M_i$ rejects, put one length-$n$ string it never queried in $A$

There is an unqueried string because the number of queries is smaller than $2^n$. The final membership assignment changes no observed answer, so $M_i$ is wrong on $1^n$

Subsequent stages preserve all frozen answers. Completing the oracle with negative answers at all unspecified strings yields

$$L_A\notin\mathrm P^A \qquad\text{and hence}\qquad \mathrm P^A\ne\mathrm{NP}^A$$

An Oracle That Makes Them Equal

Take $B=\operatorname{TQBF}$. Its PSPACE-completeness and Savitch’s theorem, developed in Lecture 9, give

$$\mathrm{NP}^{B} \subseteq\mathrm{NPSPACE} =\mathrm{PSPACE} \subseteq\mathrm P^{B} \subseteq\mathrm{NP}^{B}$$

An NP oracle machine makes polynomially long queries; each TQBF query can be answered using polynomial space, which is reused between queries

Together, these two oracle worlds establish the relativization barrier. Any argument that remained valid for every common oracle could establish neither the equality nor the separation of $\mathrm P$ and $\mathrm{NP}$