Posts

SU-CS254 FEB242025

Last edited: August 8, 2025

Key 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, 2025

We 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:

SU-CS254 JAN062025

Last edited: August 8, 2025

Theory of Computing, Computational Task

SU-CS254 JAN082025

Last edited: August 8, 2025

Notation

New Concepts

Important Results / Claims

Why stuff is great

Questions

Scratch

Let \(L \in P\), and \(M\) be the polytime TM that decides \(L\). Define \(M’\) to be \(M\) with \(q_{\text{accept}}\) and \(q_{\text{reject}}\) swapped. Fact: \(M’\) decides \(\neg L\).

SU-CS254 JAN132025

Last edited: August 8, 2025

Key Sequence

New Concepts

Important Results / Claims

Questions

Interesting Factoids