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.