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\left(n\right)}$ in time $O\left(f\right(n\left)\right)$. It is space-constructible if outputting $1^{f\left(n\right)}$ is doable in space exactly $f\left(n\right)$. 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{\}}^{*}\backslash (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\left(n\right)$ is a time-constructible function, the class $DTIME\left(f\right(n\left)\right)$ is a syntactic class, since you can effectively enumerate the TMs running in time at most $O\left(f\right(n\left)\right)$. Similarly for $NTIME\left(f\right(n\left)\right)$ -- the NTMs running in time at most $O\left(f\right(n\left)\right)$ 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 $A{C}^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\left(x\right)$ such that $x\in L\stackrel{}{\iff }R\left(x\right)\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 $\backslash \#\backslash 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 . 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\backslash \#1^{f(\mid x\mid )}: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\left(2^{n^c}\right)$. Let $Lʹ$ be the padded version of $L$, where $f\left(x\right)=2^{n^c}$. Now it's easy to see that $Lʹ$ is in $NP$: just run the $NTIME\left(2^{n^c}\right)$ 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.