Nondeterministic Polynomial-Time

An “NP machine” is a nondeterministic polynomial-time Turing machine. Then NP is the class of decision problems solvable by an NP machine such that

1. If the answer is “yes,” at least one computation path accepts.
2. If the answer is “no,” all computation paths reject.

Equivalently, NP is the class of decision problems such that, if the answer is “yes,” then there is a proof of this fact, of length polynomial in the size of the input, that can be verified in P (i.e. by a deterministic polynomial-time algorithm). On the other hand, if the answer is “no,” then the algorithm must declare invalid any purported proof that the answer is “yes.”

See the complexity zoo entry here and its complement class coNP here

Notable problems

• SAT is complete for NP — TODO citation

Known relationships

• If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.

Hardness at almost every input length

$\mathbf{NP}⊈\mathbf{io}\text{-}\mathbf{BPP}$ if some $L\in \mathbf{NP}$ is such that for every PPT algorithm $\mathcal{A}$ and all but finitely many $n$, there is an $x\in \{0,1{\}}^n$ with $\mathrm{Pr}[\mathcal{A}(x)=L(x)]<2/3$: no efficient algorithm decides $L$ on infinitely many input lengths — KMNPRY14.

Average-case hardness

$\mathbf{NP}$ is hard on average over samplable distributions if there are $L\in \mathbf{NP}$, a PPT sampler $D$ and a polynomial $p$ such that for every PPT algorithm $\mathcal{A}$ there are infinitely many $n$ with

$$\underset{x\leftarrow D(1^n)}{\mathrm{Pr}}\left[\mathcal{A}(x)\ne L(x)\right]\ge \frac{1}{p(n)},$$

the probability also over the coins of $\mathcal{A}$ — standard.

Participates in

Builds on Nondeterministic Polynomial-Time

• iO + NP ⊄ io-BPP ⇒ OWF (via Hardness at almost every input length)
• NP ⊆ AM
• NP ⊆ MA
• NP ⊆ PP
• NP ⊆ PSPACE

Produces Nondeterministic Polynomial-Time

• DLOG ⊆ NP
• FAC ∈ NP
• GapSVP ∈ NP
• OWF inversion ∈ NP
• P ⊆ NP
• PRG ⇒ Average-case hardness of NP (via Average-case hardness)
• QR ∈ NP
• RP ⊆ NP

Barriers

• No relativizing reduction from BQP to NP
• No reduction from NP to compact FHE
• No fully-black-box reduction from NP to one-round sublinear cPIR
• No Karp reduction from NP to GapSVP for γ ≥ c√n unless NP = coNP
• log n) unless coNP ⊆ AM
• No reduction from NP to OWF
• No non-adaptive reduction from NP to average-case NP hardness
• No deterministic reduction from NP to OWP
• No fully-black-box reduction from NP to size-verifiable OWF