Definition An \(n\)-ary boolean function is a function \(f:\{0,1\}^n\to \{0,1\}\).

Proposition For every boolean function \(f\) there is a propositional formula \(\varphi\) such that the function defined by \(\varphi\) is equal to \(f\).

Definition The size of a circuit is defined as the amount of and-, not-, and or-gates.

Definition Suppose that \(\{C_n\}_{n\in \mathbb{N}}\) is a family of circuits such that for every \(n\), \(C_n\) computes a boolean function of \(n\) inputs. A family computes a language \(L\) if for all \(x\in \{0,1\}^n\) we have

PP

We are going to look at a variant of NP where the acceptance criterion is probabilistic over all paths. Given a nondeterministic Turing machine the error probability is the ratio of the parths giving the wrong answer. These are probabilistic Turing machines.

Definition PP is the class of probabilistic polynomial time sets. Meaning a set \(L\) that is computed in polynomial time by probabilistic machine such that

Which implies that

Diagonalization is a proof technique first used by Georg Cantor to show that some infinities are greater than others. In proof theory it is used a lot. Most famously for proving the halting problem.

Theorem(Halting problem) Not every problem is computable.

Assume to the contrary that any problem is computable. We consider \(\{(M,x) \mid M(x)\text{ halts }\}\). Then this must also be a computable, hence we can define a machine \(N\) such that \(N(M)\) does not halt if and only if \(M(M)\) halts. Now let us think if \(N(N)\) halts. We see that \(N(N)\) does not halt if and only if \(N(N)\) halts which is a contradiction.

Relativized computation

An oracle Turing machine is a machine which has a lookup table (oracle) which has constant lookup time. This lookup table can be read from and written to.

Definition Given oracle turing machine \(M\), we let \(M^B\) be the function computed using oracle \(B\).

Definition A set \(A\) Turing reduces to \(B\) denoted \(A\leq_T^p B\), if \(A=M^B\) for some machine \(M\) working in polynomial time.

Proposition \(A\leq_m^p B \implies A\leq_T^p B\)

We know that any propositional formula has a proof. Now we are interested if every propositional formula has a “short” proof. Where “short” means polynomial given the size of the propositional formula.