Computational Complexity HT25, Approximation and the PCP theorem
Flashcards
Basic definitions
@Define an $\mathsf{NP}$ maximisation (respectively minimisation) problem and describe how $\mathsf{Max}\text{-}k\mathsf{SAT}$ and $\mathsf{Max}\text{-}\mathsf{VertexCover}$ fit into this framework.
A tuple $S = \langle c, p \rangle$ where:
- $c(x, s) : \Sigma^\ast \times \Sigma^\ast \to \mathbb N$ is a polynomial time computable “score” function where $x$ is a problem instance and $s$ is a solution
- $p$ is a polynomial
and we wish to compute the max (respectively min) score solution:
\[\text{opt}(x) = \max_{s, |s| \le p(x)} c(x, s)\](note that we don’t worry about looking for $s$, just computing the optimal value).
- $\mathsf{Max}\text{-}k\mathsf{SAT}$: $c(x, s)$ is the number of clauses of $x$ satisfied by $s$.
- $\mathsf{Min}\text{-}\mathsf{VertexCover}$: $c(x, s)$ is $ \vert s \vert $ if $s$ is a vertex cover and infinity otherwise.
Suppose $S = \langle c, p \rangle$ is an NP-approximation algorithm. What related decision problem can you consider?
Suppose:
- $S = \langle c, p \rangle$ is an NP-approximation problem
- $\alpha : \mathbb N \to [0, 1]$
@Define what it means for an algorithm $A$ to be an $\alpha$-approximation algorithm when:
- $S$ is a maximisation problem, and
- $S$ is a minimisation problem.
- Maximisation: $\alpha \text{opt}(x) \le A(x) \le \text{opt}(x)$
- Minimisation: $\text{opt}(x) \le A(x) \le \alpha \text{opt}(x)$
Example approximation algorithms
- 1/2 approx algorithm for max $k$ sat
- $1-2^{-k}$ algorithm for max exactly $k$ sat
Describe a (non-random) efficient $1/2$-approximation @algorithm for $\mathsf{Max}\text{-}k\mathsf{SAT}$.
For each variable, set it to true if it occurs more often positively in $\varphi$, and set it to false otherwise.
Describe a randomised polynomial-time $(1 - 2^{-k})$ approximation @algorithm for $\mathsf{Max}\text{-}\mathsf{Exactly}\text{-}k\mathsf{SAT}$.
Recall that (in this course) an approximation algorithm just needs to output the cost of an approximate solution.
One $(1 - 2^{-k})$-approximation algorithm just outputs $(1 - 2^{-k})m$ where $m$ is the number of clauses.
Proof: Suppose
\[\varphi = \bigwedge C_i\]Let $C _ i(x) = 1$ if the assignment $x$ satisfies $C _ i$, and $0$ otherwise. Consider this as a random variable that depends on the assignment $x$. Then
\[\mathbb E[C_i] = (1 - 2^{-k})\](since only one assignment doesn’t satisfy the clause).
Let $N _ \phi(x)$ be the number of clauses satisfied by $x$ in $\varphi$. Then
\[N_\phi(x) = \sum_i C_i (x)\]Then
\[\mathbb E[N_\phi(x)] = (1 - 2^{-k}) m\]by linearity of expectation.
PCP verifiers
Suppose:
- $L$ is a language
- $q, r : \mathbb N \to \mathbb N$
@Define a $(r(n), q(n))\text{-}\mathsf{PCP}$ verifier $V$ and what it means for $L \in \mathsf{PCP}[r(n), q(n)]$.
$V$ is a $(r(n), q(n))\text{-}\mathsf{PCP}$ verifier if:
- $V$ is efficient: On input $x \in \{0, 1\}^n$ and given random access to a string $\pi \in \{0, 1\}^\ast$ of length at most $q(n)2^{r(n)}$, $V$ uses at most $r(n)$ random coins and makes at most $q(n)$ nonadaptive queries to locations of $\pi$ and outputs $1$ for accept and $0$ for reject.
- $V$ is complete: If $x \in L$, then there exists a proof $\pi \in \{0, 1\}^\ast$ such that $\mathbb P[V^\pi(x) = 1] = 1$, the so-called “correct proof” for $x$.
- $V$ is sound: If $x \notin L$, then for every proof $\pi \in \{0, 1\}^\ast$, $\mathbb P[V^\pi (x) = 1] \le 1/2$.
- ($V^\pi(x)$ is the random variable representing $V$s output on input $x$ with random access to $x$).
$L \in \mathsf{PCP}[r(n), q(n)]$ if it has a $(O(r(n)), O(q(n)))\text{-}\mathsf{PCP}$ verifier.
What is $\mathsf{PCP}[0, 0]$?
Just use the non-probabilistic Turing machine for any language in $\mathsf{P}$.
@example~
What is $\mathsf{PCP}[0, \text{poly}(n)]$?
This follows from the standard witness characterisation of $\mathsf{NP}$.
@example~
What is $\mathsf{PCP}[\text{poly}(n), 0]$?
Ignoring the proof in the definition of a $\mathsf{PCP}$ verifier just gives the definition of $\mathsf{RP}$ but with the accept conditions the other way around.
@example~
What is $\mathsf{PCP}[0, O(\log n)]$?
Clearly $\mathsf P \subseteq \mathsf{PCP}[0, O(\log n)]$, since every $\mathsf{PCP}$-verifier is a polynomial time probabilistic TM.
$\mathsf{PCP}[0, O(\log n)] \subseteq \mathsf P$ as a polynomial time TM may guess and try all $2^{O(\log n)}$ proofs.
@example~
What is $\mathsf{PCP}[O(\log n), 0]$?
Clearly $\mathsf P \subseteq \mathsf{PCP}[O(\log n), 0]$, since every $\mathsf{PCP}$-verifier is a polynomial time probabilistic TM.
$\mathsf{PCP}[O(\log n), 0] \subseteq \mathsf P$ as a polynomial time TM may guess and try all $2^{O(\log n)}$ combinations of random bits.
@example~
What is $\mathsf{PCP}[O(\log n), O(1)]$?
This is the PCP theorem.
@example~
What is $\mathsf{PCP}[O(\text{poly}(n)), O(1)]$?
This is the “scaled-up” PCP theorem.
@example~
@State and @justify a result giving a relationship between $\mathsf{PCP}[r(n), q(n)]$ and $\mathsf{NTIME}$.
This is because a nondeterministic machine could guess the proof in $2^{O(r(n))} q(n)$ time (this is how long proofs are for $(r(n), q(n))\text{-}\mathsf{PCP}$ verifiers) and verify it deterministically by running the verifier for all $2^{O(r(n))}$ possible random bits.
PCP theorem
@State the PCP theorem.
@State a consequence (and in fact an equivalent characterisation) of the PCP theorem which implies that it’s very unlikely there are good approximation algorithms for all $\mathsf{NP}$-problems.
There exists some $\varepsilon < 1$ such that for every $L \in \mathsf{NP}$, there is a polynomial time function $f : \Sigma^\ast \to \Sigma^\ast$ from strings to 3CNF formulas such that:
- $x \in L$ implies $\text{val}(f(x)) = 1$
- $x \notin L$ implies $\text{val}(f(x)) < \varepsilon$
where $\text{val}(\varphi)$ is the best fraction of satisfying assignments achievable in $\varphi$.
As a consequence, there is some $\varepsilon > 0$ such that if there is a polynomial time $\varepsilon$-approximation algorithm for $\mathsf{Max}\text{-}3\mathsf{SAT}$, then $\mathsf P = \mathsf{NP}$.
Notes from the lecture
- Approximation and the PCP theorem
- Mitigating NP-hardness: Approximation
- Def: An NP maximisation problem (respectively minimisation) problem is $S = \langle c, p \rangle$ where $c$ is a cost function $\Sigma^\ast \times \Sigma^\ast \to \mathbb N$ is poly-time computable and $p$ is a polynomial
- Given $x \in \Sigma^\ast$, we want to compute
- Mitigating NP-hardness: Approximation
(respectively minimise) - [x] First argument to $c$ is the instance and the second argument is the solution. - [x] Can construct a corresponding decision problem $(x, k)$ where $\text{opt}(x) \ge k$. - [x] Def: Given $\alpha : \mathbb N \to [0, 1]$ (respectively $\to [1, \infty)$), we say that an algorithm $A$ is an $\alpha$-approximation to a maximisation (respectively minimisation) problem if $\alpha \text{opt}(x) \le A(x) \le \text{opt}(x)$ (respectively, $\text{opt}(x) \le A(x) \le \alpha \text{opt}(x))$. - [x] Could also consider the search version where you look for $y$, but for now just considering computing the optimal cost. - Examples: - [x] Max-$k$-SAT: How many of the clauses can you satisfy of a given CNF formula? - [x] Min-Vertex-Cover: $c(G, S) = \vert S \vert $ if $S$ is a vertex cover, infinity otherwise. - [ ] $1/2$ approximation algorithm for Max-$k$-SAT: Look at each variable and see if it occurs more positively or more negatively. Then pick the value of the variable which causes the majority to be satisfied. - [ ] Max-Exactly-$k$-SAT: Input is a $k$-CNF formula with exactly $k$ literals in each clause, want to compute the maximum number of satisfiable clauses. - [ ] Theorem: There is a polynomial time $(1 - 2^{-k})$ approximation algorithm for Max-Exactly-$k$-SAT, which just outputs $(1 - 2^{-k}) m$ where $m$ is the number of clauses. - [ ] Proof: Suppose $\varphi = \bigwedge C _ i$. Let $C _ i(x) = 1$ if the assignment $x$ satisfies $C _ i$ and $0$ otherwise. Consider this as a random variable that depends on the assignment $x$. Then $\mathbb E[C _ i] = (1 - 2^{-k})$ (since only one assignment doesn’t satisfy the clause). - [ ] Let $#\phi(x)$ be the number of clauses satisfies by $x$ in $\varphi$. Then $#\phi(x) = \sum _ {i} C _ i(x)$. Then $\mathbb E[# \phi] = (1 - 2^{-k})m$ by linearity of expectation. - Hardness of Approximation: - [x] PCP (probabilistically checkable proofs). - [x] Def: A PCP verifier is a probabilistic polynomial-time oracle machine $V$ with oracle access to a proof $\pi$. Queries are made to the bits of $\pi$. We say that $V$ has randomness complexity $r(n)$ and query complexity $q(n)$ if on any input $x$ of length $n$, $V$ uses at most $r(n)$ random bits and makes at most $q(n)$ non-adaptive queries. - [x] (assuming non-adaptiveness doesn’t matter too much, e.g. if the query complexity assuming adaptive queries is constant, then it’s possible to just make all $2^n$ possible non-adaptive queries) - [x] Def: Let $r$ and $q$ be functions $\mathbb N \to \mathbb N$. Then $PCP[r(n), q(n)]$ is the class of languages $L$ for which there is a PCP verifier $V$ such that: - [x] (Completeness): If $x \in L$, then there is a proof $\pi$ such that $\mathbb P[V^\pi(x) = 1 ] = 1$. - [x] (Soundness): If $x \notin L$, then for all proofs $\pi$, $\mathbb P[V^\pi(x) = 1] \le 1/2$. - Examples: - [x] $PCP[0, 0] = P$ - [x] $PCP[0, \text{poly}(n)] = NP$ - [x] $PCP[\text{poly}(n), 0] = coRP$ - [x] $PCP[0, O(\log(n))] = P$, try all possible - [x] $PCP[O(\log(n)), 0] = P$, try all possible, - [x] PCP Theorem: $PCP[O(\log n), O(1)] = NP = PCP[O(\log n), 3]$. - Proof: Difficult. - [x] Theorem: $\exists \epsilon > 0$ such that Max-$k$-SAT is $(1 - \epsilon)$-hard to approximate if $NP \ne P$. - [ ] Proof: Let $\epsilon > 0$ be a small enough constant. We construct a polynomial time reduction $f$ such that $\phi \in SAT$ implies that $f(\phi)$ is a satisfiable $k$-CNF. If $\phi \notin SAT$, then $\text{opt}(f(\phi)) \le (1 - \epsilon)m$, where $m = \vert f(\phi) \vert $, i.e. the number of clauses in $f(\phi)$. - [ ] Let $V^\pi$ be a PCP verifier for SAT that uses randomness at most $C\log n$ and makes $k$ queries to $\pi$ (the existence of this verifier follows from the PCP theorem). - [ ] $f(\phi) = \bigwedge _ {r \in {0, 1}^{c \log n} } \psi _ r$ where each $\psi _ r$ is a $k$-CNF that computes…