Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / PCP
Tags: fromMath mathToDef mathToSee examplesSwitchExample1 hasSeenConjDef

Definition: The maximum fraction of classes that can be satisfied by any assignment to \(\phi\)'s variable.
Page: 238
Chapter: 11
Section: 1
Variables: \(\phi\) a 3CNF formula
Notation: \(\text{val}(\phi)\)

Name: A \(\rho\)-approximation algorithm
Definition: An algorithm \(A\) such that \(A(\phi)\) outputs an assignment satisfying at least \(\rho\text{val}(\phi)m\) of \(\phi\)'s clauses
Page: 238
Chapter: 11
Section: 1
Variables: \(\phi\) a 3CNF formula with \(m\) clasuse.
\(\rho<1\)

Name: MAX-3SAT
Definition: Given a 3CNF formula, output an assignment satisfying the maximal number of clauses.
Page: 239
Chapter: 11
Section: 1

Q: MAX-3SAT have a [...]-approximation algorithm in \(P\).
A: \((7/8-\epsilon)\)
Page: 239
Chapter: 11
Section: 1
Index: 2
Kind: Ex

Name: MIN-VERTEX-COVER
Definition: Given a graph, output a vertex-cover as small as possible.
Page: 239
Chapter: 11
Section: 1
Index: 3
Kind: Ex

Q: MIN-VERTEX-COVER admits a [...]-approximation PTIME algorithm.
A: 1/2
Page: 239
Chapter: 11
Section: 1
Index: 3
Kind: Ex

Q: \([...]=\text{PCP}([...])\).
A: \text{NP}; \log n,1
Page: 241
Chapter: 11
Section: 2
Index: 5
Kind: Theo
Name: The PCP Theorem

Name: A language in \(\text{PCP}(r(n),q(n))\)
Definition: A language, such that there are some constants \(c,d>0\) such that \(L\) has a \((cr(n),dq(n))\)-PCP verifier.
Page: 241
Chapter: 11
Section: 2
Variables: \(q,r\mathbb N\to\mathbb N\).
Index: 4
Kind: Def

Question: \(\mathbf{PCP}(r,q)\subseteq\)
Answer: \(\mathbf{NTIME}\left(2^{O(r(n))}\right)\).
Page: 241
Chapter: 11
Section: 2
Variables: \(q,r\mathbb N\to\mathbb N\).
Index: 3
Kind: Rem

Name: Problem in \(\pmb{PCP}(poly(n),1)\)
Page: 242
Chapter: 11
Section: 2
Index: 7
Kind: Ex
Example: Graph non-isomorphism

Q: \([...]=\text{PCP}([...])\).
A: \text{NEXP}; poly(n),1
Page: 242
Chapter: 11
Section: 2
Index: 8
Kind: Theo

Name: Hardness of approximation view
Definition: There exists \(\rho<1\) such that for every \(L\in\pmb{NP}\), there is a PTIME function \(f\) sending elements of \(L\) to satisfiable 3CNF and words not belonging to \(L\) to CNF with less than \(\rho\) satisfiable clause.
Page: 242
Chapter: 11
Section: 2
Index: 9
Kind: Theo

Name: \((r(n),q(n))-\pmb{PCP}\) verifier
Definition: \(V\) uses \(r(n)\) random bits to chose \(q(n)\) bits to query from a string \(\pi\),
Page: 241
Chapter: 11
Section: 2
Variables: \(q,r:\mathbb N\to\mathbb N\).
Index: 4
Kind: Def
Definition2: \(V\) is complete for some \(\pi\in\{0,1\}^*\)
Conjdef: A PTIME probabilistic algorithm \(V\) such that
Definition3: \(V\) is sound for every \(\pi\in\{0,1\}^*\) with probability at least \(1/2\)