The "complexity" of the Turing machine state specification

Question

Suppose we want to represent some arbitrary Boolean function $f(x_1,x_2,...,x_N)$ on $N$ bits. We can explicitly specify such a representation using the disjunctive normal form. For "most" Boolean functions, this representation will be of length exponential in $N$, and incompressible (as per Shannon). We will assume we have chosen such an incompressible function.

We can build a Turing machine corresponding to this circuit, which ACCEPTs an input $\mathbf{x}$ if and only if $f(\mathbf{x}) = 1$. We can then ask what complexity such a Turing machine would have.

Now, the subtlety is: since our function is incompressible, any attempt to physically represent it must, naively, be "exponentially large"... in some sense. But we can "hide" the "exponentialness" of this in various places based on how we define our Turing machine, which would appear to change its computational complexity.

How does complexity theory handle this case?

Now, if we were treating the DNF as part of the input, we could create a Turing machine and feed our DNF and some bitvector to evaluate as an "exponential-length" input. We would then know that our Turing machine would take time $O(2^N)$ just to read the DNF, so accounting for everything relative to $N$, we're in (at least) exponential time.

But, as we are "building the circuit into" the specification of the Turing machine itself, we can recognize this language in $O(N)$:

• Check if the first bit is 0 or 1. Then, we have a branch to two states corresponding to $f(0,x_2,...,x_N)$ and $f(1,x_2,...,x_N)$, and transition according to the input.
• Repeat with the second bit. For each possibility, we have two more states, yielding four states total: $f(0,0,...,x_N)$, $f(0,1,...,x_N)$, $f(1,0,...,x_N)$, and $f(1,1,...,x_N)$.
• Continue branching until the end, and then ACCEPT/REJECT according to the specification of our function.

Of course, our Turing machine is "pathological" in that it now requires an exponential number of states. But, technically, since time complexity does not take this into account, it looks like we've gone from $O(2^N)$ to $O(N)$.

We can "fix" this to obtain a Turing machine with only one nontrivial state that recognizes the language in $O(1)$! Simply change the alphabet to be of size $2^N$, so that bitvector is viewed "atomically" as a single entry in the alphabet. Then we encode membership in our Boolean function by a single state transition to ACCEPT or REJECT based on the input. Of course, now the problem is that our "$O(1)$ machine with one state" has an exponentially large state transition table.

My question: What is the complexity of our language, expressed relative to $N$? Naively, I would like to say it's in EXPTIME, since the "exponential speedups" given by the last two Turing machines are clearly pathological, but I don't normally see this metric accounted for anywhere in complexity theory.

In general, how does complexity theory handle this? Are such pathological machines explicitly excluded in the main results of the field, and if so, what criterion do we use for excluding them?

Answer 1

Complexity theory typically handles asymptotics, not finite cases. In particular, complexity theory looks at the asymptotic running time as a function of $N$. If you have only a single fixed $N$, then the standard framework doesn't apply. It's not possible to talk about the running time being asymptotically an exponential function of $N$, because with only a single value of $N$, it is just a fixed constant; it's not a function of anything. Complexity classes like EXPTIME are defined in terms of these asymptotics, so they aren't applicable if you have just a single function you want to compute, for a single fixed value of $N$.

So, if you want to apply the machine of complexity theory, you need to consider a family of boolean functions, one for each $N$, and a single Turing machine that computes all of them. Then you can characterize the running time of that Turing machine as a function of $N$ (the length of the input). At that point, there is no opportunity to "hide exponentialness" in the definition of the Turing machine, because you need to pick a single fixed Turing machine that computes all of them, and your idea for "smuggling exponentialness" can't be done if you have a fixed Turing machine. Whatever you do, you only get a constant-factor speedup.

---

I have seen some formalizations that characterize the complexity not by the running time of the machine, but by the running time plus the length of the machine specification. For instance, in the RAM model, you can use the running time of the algorithm plus the length of the code of the program. Then, you can measure how this behaves as a function of $N$. You can even characterize it for a single $N$, but then you're not dealing with asymptotics or complexity theory or complexity classes like EXPTIME; you're just saying that the least-complexity program to implement this one function has time+size equal to such-and-such. For instance, this approach is sometimes used in theoretical cryptography (called "concrete security"), where we care about a single value of $N$, rather than the asymptotic behavior as $N \to \infty$. But again, then you can't talk about complexity classes like P or EXPTIME.