CSC 422 Fall 2013

Tutorial Notes Home Course Webpage

Tutorial 2: Non-uniform Computation

23 Sep 2013

Today's tutorial concerns non-uniform models of computation

Context within the course, definitional motivation

The ultimate goal of the course is to devise cryptosystems with the property that no computer program can compromise their private or integrity. To formalizing statements of this kind involves formalizing a model of computation. And to have confidence in the guarantees of these theorems, it's important that we take the most expansive and powerful notion of computation into consideration.

The first and most mathematically natural formalization of computation - that of Turing machines - is not the strongest formalization of computing we can devise. In this note we define and prove some properties about the non-uniform models of computation, non-uniform turing machines and circuits.

A 'vanilla' Turing machine computes in manner that is uniform with respect to its input lengths. It follows an identical set of instructions no matter what length of input it receives.

Were you writing a computer program in practice, you are probably focussing on inputs of a particular size, and your program is likely to take into account some tacit knowledge about these inputs; maybe statistics about the inputs in question, maybe just some information you're encoding on a hunch.

A non-uniform Turing machine is a TM that gets an advice string for inputs of various categories (which you should imagine as categories of your choice as algorithm designer). In our definition, we'll group the inputs by input length (because we need a definition applicable for all problems).

The next question is how much advice is reasonable? Since there are $2^n$ inputs of length $n$, an advice string of exponential size could encode the answers of all computations and shouldn't be seen as advice. So we'll consider advice strings of polynomial size (i.e. $O(n^c)$ for some $c$) (we could allow the strings to be any sub-exponential, e.g. $O(2^{\sqrt{n}})$, but we won't see examples where this quantitative difference is important, so we just stick with polynomial advice).

Definition (non-uniform TMs)

A polynomial-time Turing machine with polynomial-sized advice is a polynomial time Turing machine $M$ (i.e. a machine such that $t_M(n) = O(n^c)$ for some $c$) as well as an infinite collection of advice strings $\{a_n\}_{n \in \mathbb{N}}$ of polynomial size (i.e. $|a_n| = O(n^d)$ for some $d$).

$(M, {a_n}) \in P/poly$ decides a language $L \subset \{0,1\}^*$ if \[ \forall x \in \{0,1\}^* \ M(x, a_{|x|}) = \chi_L(x) \] (Where $\chi_L$ is the indicator function for $L$, i.e. $\chi_L(x) = 1$ if and only if $x \in L$).

The set languages decided by of polynomial-time Turing machines with polynomial-sized advice is denoted $P/poly$; we'll refer to $(M {a_n})$ as a $P/poly$ machine.

Non-uniformity and randomness

Implicitly, the definition given above does not give the TM the benefit of random bits. Given our motivation above, it should be clear that we do want to equip our model of computation with whatever might be helpful, however the power of non-uniformity supercedes the power of being able to toss random coins. Let's formalize that now.

First we must recall our notion of randomized computation.

Definition

A language $L$ is said to be in $BPP$ (bounded-error probabilistic polynomial time) if there is a Turing machine $M$ with a random tape such that \begin{equation} \label{eq:bpp_acceptance} \forall x \in \{0,1\}^* \ \Pr_r[M(x;r) = \chi_L(x)] \geq 2/3 \end{equation} The probability above is over the random coins of the algorithm. No matter the input, the machine is more likely to output the correct answer than the incorrect answer.

The following theorem formally states that non-uniformity (i.e. advice) is more powerful than randomness

Theorem

\[ BPP \subseteq P/poly \] The proof of this theorem involves choosing the advice to be a specific setting of the random tape (i.e. the best possible). We could already, for each input length, choose an $r^*_n$ so that $M'(x) = M(x;r^*_n)$ is correct on $2/3$ of all $x \in \bit^n$. Of course we need to be correct on each $x \in \bit^n$. However, if we first amplify the correctness of our initial algorithm (done easily by taking the majority result of independent trials -a technique sometimes referred to as parallel repitition), there will be a random string that works for all $x$'s.

Proof

Let $L \in BPP$ as decided by $M$ (i.e. $M$ and $L$ satisfy \eqref{eq:bpp_acceptance}).

Claim 1

$\exists M'$, also a $BPP$ machine, such that \begin{equation} \label{eq:bpp_amplified} \forall x \in \{ 0,1 \}^* \ \Pr_r[M'(x;r) = \chi_L(x)] > 1 - 2^{-n} \end{equation}

Claim 2

$\forall n \exists r^*_n$ such that \begin{equation} \forall x \in \{ 0,1 \}^n \ M'(x;r^*_n) = \chi_L(x) \end{equation}

The $P/poly$ machine for $L$ is $(M', { r^*_n }_{n \in \mathbb{N}})$. That $M'$ consumes at most polynomial time is immediate from $BPP$; that $r^*_n$ are also polysized is implied by $M'$ being a $BPP$ machine, since a polytime bounded machine can consume at most polynomially many random bits.

Proof of Claim 1

Let $M'(x; r_1,\ldots,r_m)$ = $Majority{ M(x;r_1), \ldots, M(x;r_m) }$ Arguing the correctness of $M'$ is straightforward given properties of the binomial distribution: \begin{align} \Pr[M'(x; r_1, \ldots, r_m) = \chi_L(x) ] &= \Pr[ Bin(m, 2/3) > m/2 ] \notag \\ &= \Pr[ |Bin(m,2/3) - m/2| > m/6 ] \label{eq:binomial_tail} \end{align} It is well known (e.g. see Chernoff Bound)that for $m = O(n^2)$ gives that \eqref{eq:binomial_tail} is $O(2^n)$.

Proof of Claim 2

Fix $n$. Suppose the total number of random bits consumed by $M'$ is $\ell(n) = \ell$. Let $T$ be an $2^n$ by $2^\ell$ table, with rows labelled with elements of $\bit^n$ and columns labelled with elements of $\bit^\ell$ and whose $(x_i, r_j)$'th entry is $1$ if $M'(x_i;r_j) = \chi_L(x_i)$ and $0$ otherwise. \eqref{eq:bpp_amplified} tells us that more than a $1 - 2^{-n}$ fraction of the entries are $1$. Since there are only $2^n$ rows, there is at least one column of all $1$'s. Letting $r^*_n$ be any such column completes the proof.