Computational complexity classes not based on input size?

Question

Computational complexity classes, such as $P, NP, PSPACE$, etc, are defined according to the factory by which computational time increases, as the input size $n$ increases.

But this doesn’t allow us to talk about the complexity of a particular problem (i.e. for a particular $n$).

For example, I believe that “generalized chess”, i.e. on an $n\times n$ board, is $NP$-hard. But this only tells us something about how the computational time of generalized chess increases as $n$ goes to infinity. It doesn’t tell us anything about how hard $8\times 8$ chess is.

On the other hand, simply giving a number, denoting the amount of steps required to solve $8\times 8$ chess with a Turing machine, is not very insightful.

Is there a different classification-scheme/framework for analysing the computational complexity of problems, that doesn’t refer to the input size $n$, that allows us to analyse e.g. the complexity of $8\times 8$ chess?

Answer 1

No, not really: there's no framework for this that turns out to be very useful. There is a reason that in theoretical work we often use asymptotic complexity.

In principle, you could talk about the concrete complexity of the problem of chess on a 8x8 board. One way to measure that would be to use the worst-case running time of the fastest program to solve chess on a 8x8 board: not the asymptotic running time, but the actual wall-clock time, measured in seconds. However, this has multiple problems. One problem is that it is obviously super-specific to a particular computer: if I buy a different computer, the wall-clock time might be very different, even though I haven't changed the algorithm. So now the running time is no longer a property of the algorithm; it also depends intimately on which computer I run it on.

Or, perhaps we could count the number of instructions executed. But now that will depend on the particular computer architecture; when we compile to x86, the number of instructions might be different than when we compile to ARM. So the complexity still depends on the computer.

Finally, there is the problem that it is very hard to reason about this number through theoretical analysis. Given some pseudocode, can you analyze how many instructions or how many seconds it will take to run that pseudocode? That's very hard, since the pseudocode first has to be implemented in some language, then compiled to machine language, then run. (And good luck reasoning about the effect of caches and the memory architecture on the time it takes to, e.g., perform a single read or write to memory; that's very hard to predict.) At best, it gets super messy; at worst, it's just not predictable in a reasonable way.

If you read Knuth, you'll find that he tries to do this kind of analysis. He defines an artificial computer architecture called MIX, which is fully specified. He then implements his algorithms carefully in MIX machine language, and finally mathematically analyzes the number of MIX instructions the algorithm might take. If you go through some of his demonstrations you'll see just how painful and messy it is. He ends up doing this only for some pretty simple algorithms, and the calculations are still ugly; doing that for something as complex as a chess algorithm sounds horrendously painful.

Finally, there's the problem that we don't know what is the optimal program for playing 8x8 chess. That's a famous open problem.

So, yes, in principle, it is possible to reason about running time without relying on asymptotics. In practice, it usually gets so messy that you drown in details and have a hard time extracting useful insights.