SU-CS254 FEB122025
Last edited: August 8, 2025Key Sequence
Notation
New Concepts
- circuits
- complexity measures of circuits
- circuit family
- p-uniform family
- uniform (complexity theory)
- size complexity
P/poly
- advice-taking TM
Important Results / Claims
Questions
Interesting Factoids
SU-CS254 FEB192025
Last edited: August 8, 2025Key Sequence
Notation
New Concepts
Important Results / Claims
- BPP ⊂ P\Poly
- \(\text{BPP} \subseteq p / poly\)
- if \(\text{SAT} \in p / poly\), then polynomial hierarchy collapses to the second level; that is pi2=sigma2
Questions
Interesting Factoids
SU-CS254 FEB242025
Last edited: August 8, 2025Key Sequence
Notation
New Concepts
Important Results / Claims
Questions
Interesting Factoids
An Anthropomorphic View of NP
For some string \(x\), and language \(L\). We wonder:
\begin{equation} x \in^{?} L \end{equation}
We can consider NP as a two party game, whereby:
- prover: looks at \(x, L\), and sends some proof \(w\) for \(x \in L\)
- verifier: does some polytime computation, and either accepts or rejects
We want to make sure that this system follows the following patterns:
SU-CS254 FEB262025
Last edited: August 8, 2025We are here to prove a theorem.
The number of satisfying assignments is a problem solvable in IP(k).
Consider some 3SAT formula:
\begin{equation} \phi\qty(x) = \qty(x_1 \vee x_3 \vee \neg x_9) \wedge \qty(\neg x_2 \vee \neg x_5 \vee x_{50}) \wedge \dots \end{equation}
where \(\phi\qty(x)\) has exactly \(k\) satisfying assignments. This expression has \(n\) variables and \(m\) clauses. Notice that: \(x_1 \vee x_3 \vee \neg x_{9}\) if and only if \(x_1 = 0, x_3 = 0, x_{9} = 1\). This has the following properties: