Details for the IKW Theorem

The proof of the IKW Theorem I gave in class was a bit sketchy; let me discuss two points about it, raised by Or and Pranjal.

1. The first point, raised by Or, was about appealing to the Impagliazzo-Wigderson Theorem (or implicitly, the Nisan-Wigderson Theorem). Normally when one thinks about that theorem one thinks of the statement, "If there is a language $L \in E$ such that $L \not \in \bigcup_c \SIZE(n^c)$, then $BPP \subseteq \bigcap_{\epsilon} DTIME(2^{n^\epsilon})$.

However, this is not what the IKW Theorem appeals to; you should think of that as a corollary of the IW/NW Theorems. The Theorems themselves are input-length-specific; e.g., for Nisan-Wigderson, the statement we're using is of the form "Let $C$ be a circuit on $n$ bits of size $n^c$, and let $f : \{0,1\}^{n^{1/10c}} \to \{0,1\}$ be a function such that every size-$n^{2c}$ circuit has correlation at most $1/n^{2c}$. Then [some explicit PRG outputting $n$ bits based on $f$'s truth table and designs] $1/10$-fools $C$."

2. The second point, raised by Pranjal, was about the uncareful (indeed, possibly incorrect) way I explained the derandomization of $MA$ that comes out of assuming $NEXP \neq EXP$. The wrong way to say it is to start with a fixed language in $MA$ and then deduce that Arthur's $n^c$-time randomized part can be replaced by some other $NTIME(2^{n^a})$-time algorithm (with advice). That is, of course, pointless, if $a \geq c$, since Arthur could just enumerate all possible random strings. Rather, the key is to show that all of $MA$ can be done by a nondeterministic (advice-taking) Arthur who uses fixed-exponential nondeterministic time.

In other words, the correct key lemma is:

$NEXP \neq \EXP \Rightarrow \exists c, MA \subseteq io-[NTIME(2^{n^c})/n]$.

This is nontrivial because the same $c$ works for all languages in $MA$, regardless of their polytime complexity. And the proof of this uses the appeal to the length-specific IW Theorem described in Point 1 above.

Why there isn't a simpler proof of IKW

A question raised in class today was, Why can't we prove the IKW Lemma, $NEXP \subseteq P/poly \Rightarrow NEXP = EXP$, via techniques similar to Meyer's Lemma, $EXP \subseteq P/poly \Rightarrow EXP = PSPACE$?

(Recall, btw, that IKW actually get $NEXP = MA$ and Meyer actually gets $EXP = \Sigma_2$.)

In discussing it with Or and Pranjal after class, it seems the answer is the following. In the Meyer Lemma, for a fixed $EXP$ machine, we considered the map taking the index of tableau window into the tableau window contents. That map is in $EXP$, hence in $P/poly$. So there exists a circuit $C$ of some size $n^k$ computing the map. Given x, we enumerate all circuits of that size, and accept iff one of them implicitly describes an accepting tableau; this is doable in $PSPACE$.

Why doesn't this work for $NEXP$? For $NEXP$ computations, there may be multiple accepting tableaus. Not a problem so far. Certainly the $PSPACE$ algorithm still makes sense: enumerate all circuits of some fixed poly-size, and if one of them implicitly describes an accepting tableau, accept. The question is, if $x$ is in the language, will there be a fixed poly-size circuit describing an accepting tableau?

One has to be careful. There is no longer a clear meaning for "the map that takes a tableau window index to the tableau window contents", since there are multiple valid tableaus. Perhaps that's okay; perhaps we can allow for "multivalued functions". But still, there isn't a clear meaning for "this map is computable in $NEXP$ and hence in $P/poly$". The reason is, the usual meaning of an NTM computing a function is that some branches reject, and the ones that accept output valid answers. Such a model indeed computes a multi-valued function. However since it's not a decision problem (a language), it's not clear how we can get anything out of the assumption $NEXP \subseteq P/\poly$.

One way around this, as Or suggested, would be to make everything single-valued by looking at the lexicographically least accepting tableaus. Unfortunately, as we saw on Homework 2, this lexicographically least satisfying assignments characterize the lass $P^{NP}$, not $NP$. All is not lost, though; a paper of Bourke uses such ideas to show $EXP^{NP[t(n)]} \subseteq P/poly \Rightarrow EXP^{NP[t(n)]} = MA$ (where the notation indicates that the $EXP$ machine makes $t(n)$ queries to the oracle). This is related to Buhrman and Homer's old extension of Karp-Lipton: $EXP^{NP} \subseteq P/poly \Rightarrow EXP^{NP} = \Sigma_2$.

Misc. Definitions

In the lectures we've skipped some technical definitions so as to not get bogged down. But these are good things to know; they'll come up again and again if you study Complexity Theory.

1. Constructibility:A function $f : \mathbb{N} \to \mathbb{N}$ is time-constructible if there is a DTM which, on input $1^n$, outputs $1^{f(n)}$ in time $O(f(n))$. It is space-constructible if outputting $1^{f(n)}$ is doable in space exactly $f(n)$. As mentioned in class, we also invariably restrict attention to time bounds that are at least $n$ and space bounds that are at least $\log n$. In this case, every non-ridiculous time bound you would ever use is time-constructible, and similarly for space. The Time and Space Hierarchy Theorems require constructibility.

2. Promise problems: This is a generalization of a "language". A promise problem is a pair $(Y,N)$ of disjoint subsets of $\{0,1\}^*$. A TM "decides" the promise problem if it accepts all strings in $Y$ and rejects all strings in $N$. Note that a promise promise is a language iff $Y \cup N = \{0,1\}^*$. The name "promise" here refers to the fact that you can think of the TM as being "promised" that the input string is always in $Y \cup N$. Generally speaking, if there is an "efficient" algorithm for checking if $x \in Y \cup N$ then the promise problem is not much different from a language (one can put the "easily decidable" strings in $\{0,1\}^* \setminus (Y \cup N)$ into either $Y$ or $N$, say).

3. Syntactic/semantic classes: This is not a 100% rigorous definition; we illustrate it via examples. A complexity class defined via time-bounded machines (TMs, NTMs, counting TMs, etc.) is said to be syntactic if there is an "effective enumeration" of the machines defining the class. For example, if $f(n)$ is a time-constructible function, the class $DTIME(f(n))$ is a syntactic class, since you can effectively enumerate the TMs running in time at most $O(f(n))$. Similarly for $NTIME(f(n))$ -- the NTMs running in time at most $O(f(n))$ are effectively enumerable. Classes like $P$, $NP$, $PSPACE$ are "syntactic". Syntactic class have Hierarchy Theorems and they also tend to have "generic complete problems". A semantic class is one which is not syntactic; generally, this means it is defined by a machine class "with a promise". The classic example is $BPP$: Here there is no way to effectively enumerate randomized TMs with the property that for each $x$ they either accept with probability at least $3/4$ or reject with probability at least $3/4$. (Indeed, checking whether an RTM has this property is undecidable.) Instead, languages in $BPP$ are defined only by machines $M$ that satisfy the promise "$M$ is a BPP machine".

4. Promise classes: For semantic classes like $RP$ and $BPP$ there is an associated "promise class" of promise problems, denoted $prRP$, $prBPP$, etc. For example, $prRP$ is the class of all promise problems $(Y,N)$ such that there is a polynomial-time RTM which accepts all strings $x \in Y$ with probability at least $1/2$ and accepts all strings $x \in N$ with probability $0$. The RTM may have any behavior on strings not in $Y \cup N$.

5. Uniformity: Again, this is not 100% well-defined, but a complexity class is said to be uniform if it is defined by one machine that operates for all input lengths. It is said to be nonuniform if there is a different machine defining it for each input lengths. Roughly, classes with TM-based definitions are "uniform", and classes with circuit-based definitions are "nonuniform".

6. Reductions: We've talked about how it is important to specify the complexity of reductions (poly-time, log-space, even $AC^0$), but there's also another distinction. A many-one (or Karp) reduction $R$ from $L$ to $L'$ is one which maps $x$ to $R(x)$ such that $x \in L \iff R(x) \in L'$. An oracle (or Cook) reduction $R$ is one which solves $L$ by using an algorithm for $L'$ as an oracle. Having a Karp reduction is "stronger" than having a Cook reduction, and we generally define completeness for complexity classes in terms of having a Karp reduction because we can: e.g., all textbook $NP$-completeness reductions are many-one. But sometimes it's better to define completeness in terms of Cook reductions; for example, as we saw in class with $\#\P$.

7. -hard: For a class $C$ we said that $L$ is $C$-complete if: (a) $L \in C$; (b) every problem in $C$ reduces to $L$. We say that $L$ is $C$-hard when (b) holds.

8. Self-reducibility: A language $L$ is said to be downward self-reducible if one can decide $x \in L$ efficiently using an oracle for $L$ on instances of size $< |x|$. This sounds funny, but it makes sense. The classic example is $SAT$: If you have a black box which can solve any $SAT$ instance of size at most $n$, you can use it to efficiently solve any instance of size at most $n+1$; you use the classic trick of setting $x_1$ to $0$ and checking satisfiability, and setting $x_1$ to $1$ and checking satisfiability. A language $L$ is said to be randomly self-reducible if one can decide $x \in L$ efficiently with high probability using an oracle for $L$ which works with high probability on randomly chosen instances. An example (as we'll see at some point in class) is the 0-1 PERMANENT problem: If you can solve randomly chosen 0-1 PERMANENT instances with high probability, you can actually solve all 0-1 PERMANENT instances with high probability.

9. Padding: Padding is the general idea of taking a language $L$ and considering the language $L' = \{ x\#1^{f(|x|)} : x \in L \}$, where $f$ is some fast-growing functions. I.e., it's the idea of "padding" all inputs with a large number of "blanks". It is used for classic upward collapse results such as "$NP = P \Rightarrow NEXP = EXP$". To see this, suppose $NP = P$. Let $L$ be a language in $NEXP$; say it's in $NTIME(2^{n^c})$. Let $L'$ be the padded version of $L$, where $f(x) = 2^{n^c}$. Now it's easy to see that $L'$ is in $NP$: just run the $NTIME(2^{n^c})$ algorithm for $L$, which is now "polynomial time" because the input length in $L'$ has been padded. Hence by assumption, $L'$ is in $P$. But then clearly $L$ is in $EXP$: to decide $x \in L$ in exponential time, just pad $x$ and then run the $P$-algorithm for $L'$.

10. Succinctness: This is the spiritual opposite of padding. For some languages $L$, there is a version $L'$ where the inputs for $L$ are succinctly described. The classic example is where $L$ is CIRCUIT-VALUE, and $L'$ is SUCCINCT-CIRCUIT-VALUE. Here, an input $E$ for $L'$ is a "succinct encoding" of an (exponentially large) circuit $C$: The input $E$ itself is a circuit, which on input $i$ "outputs the $i$th gate in $C$" -- its type (AND, OR, NOT, input, output), and the indices of the gates that feed into it. Typically, the "succinct" version of a complete language is itself complete for the "exponentially larger" class. For example, you can check that since CIRCUIT-VALUE is $P$-complete, SUCCINCT-CIRCUIT-VALUE is $EXP$-complete. And since SAT is $NP$-complete, SUCCINCT-SAT (where the input is a circuit describing an exponentially long formula) is $NEXP$-complete.