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?