SUBJECT: A tighter version of Thm 4.1 


THM 4.1 (p. 128) asserts a separation between $P/\ell'$
and $P/(\ell'+\delta)$ for every $\ell',\delta:\N\to\N$ such 
that $\delta$ is unbounded and $\ell'(n)+\delta(n)\leq 2^n$.

In a class meeting (Dec'14), I was asked whether 
we can replace $\delta$ by one. It seems that we can...


[If you are interested in a small project -- stop reading here
and try to find the proof of the foregoing assertion by yourself.
Otherwise, you may just continue reading.] 


The current proof of Thm 4.1 is wasteful in failing all machines that 
take advice of length $\ell'$ on all but finitely many input length.
(Hence, only the first $2^{\delta(n)}$ machines are failed on
input length $n$, and we must use unbounded $\delta$ to fail all machines.)

This is wasteful since it suffices to fail each machine on infinitely
many input lengths (rather than on all but finitely many input lengths).
Hence, we consider a partition of $\N$ to infinitely many infinite sets,
and assign each possible machine (that takes advice) to one such set
(e.g., the $j$th machine can be assigned to the lengths
that are odd multiples of $2^j$). We shall use the lengths assign
to each machine in order to fail it at least one input of each
of the corresponding lengths. The set of functions that will be
used for this purpose is exactly the set used in the orioginal proof
(defined by exactly the same algorithm as in the original proof),
except that here we set $\delta=1$. Hence, we get: 

THM 4.1' (i.e., Thm 4.1, revised):
For every $\ell:\N\to\N$ such that $\ell(n)\leq 2^n$,
it holds that $P/\ell$ strictly contains $P/(\ell-1)$.

PF: Consider algorithm $A$ that given advice $a_n\in\bitset^{\ell(n)}$
and input $i\in[2^n]$ outputs the $i$th bit of $a_n$ if $i\leq|a_n|$
and outputs zero otherwise. For every sequence ${\ov a}=(a_n)_{n\in\N}$,
algorithm $A$ defines a function $f_{\ov a}$ in $P/\ell$,
and different $\ov a$'s yield different functions. 
We shall show that some of these functions are not in $P/(\ell-1)$.

First note that for each machine $M$ that takes advice of length $\ell-1$
and each input length $n$, machine $M$ can compute at most $2^{\ell(n)-1}$
different functions on inputs of length $n$. 

In particular, for each machine $M$ that takes advice of length $\ell-1$,
and every $n\in\N$, we can find $a_n\in\bitset^{\ell(n)}$ 
such that for every $\ov a$ that is compatible with $a_n$ 
(i.e., $a_n$ is the $n$th element in $\ov a$)
machine $M$ fails to compute $f_{\ov a}$ on some input of length $n$
no matter what $\ell(n)-1$-bit long advice is given to it.

Using a partition of $\N$ to infinitely many infinite sets,
we associate to each machine $M$ (as above) a disjoint set of lengths, 
denoted $I_M$, and determine $a_n$ for every $n\in I_M$ such that $M$ fails 
(in computing each of the corresponding $f_{\ov a}$)
on all lengths in $I_M$ no matter what advice is given to it.
(Note that $M$ fails on each input length $n\in I_M$ 
no matter how $a_m$ is set for $m\not\in I_M$.)
Combining all these determinations (i.e., determining each $a_n$
in order to fail the machine associated with length $n$
(i.e., machine $M$ such that $n\in I_M$)), we obtain a function $f_{\ov a}$
that fails each possible machine that takes an $\ell-1$-bit advice
no matter which advice is given to it.
QED


CONCEPTUAL DIGEST: Note that the above proof presents functions that are 
computable in $P/\ell$, but are not computable by any machine that takes 
advice of length $\ell-1$ regardless of the running time of these machines.
Hence, Thm 4.1' generalizes and strengthens Thm 1.13. 

TECHNICAL DIGEST: As stated in the second paragraph of the proof,
for each machine $M$ that takes advice of length $\ell-1$ and $n\in\N$, 
machine $M$ can compute at most $2^{\ell(n)-1}$ different functions 
on inputs of length $n$. The problem, which we faced at that point,
is that different machines may be used for computing different functions, 
and so just counting the number of possible functions on $n$-bit inputs
computable by all machines (as done in the original proof) will not do. 
The solution is that it suffices fail different machines on different 
input length (and so avoid the foregoing counting problem).

TECHNICAL NOTE: In the proof, each machine is failed on infinitely
many input length, whereas (by the definitions used in the book) 
failing each machine on one input suffices. This is done in order
to support alternative definitions (which appear in other sources)
in which complexity classes are defined while allowing finitely many 
erroneous inputs. Under such definitions, we need to fail each machine 
infinitely often...

(Note that when using the definition as in the book (i.e., no finitely 
many errors), the failure on a single input cannot be corrected
by modifying the failing machine on this input, since the resulting
modified machine is also ruled out at a latter stage of the enumeration
of all machines.) 

I prefer the version used in the book (i.e., no exceptional inputs),
but an advantage of the other version is that one does not have to worry 
about pathologically short inputs when presenting transformations between
complexity classes.

ACK: Thanks to Tom Gur and Roei Tell for suggesting improvement 
to a prior version of this text.