2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Your question is a little confusing because of the terminology you use. In the language of computational complexity, "generalized chess" is a problem, and 8x8 chess (which you're calling a "problem") is an instance of that problem. Also, what do you mean by "solving 8x8 chess"? The answer to any fixed instance is just some fixed string, and you correctly say that this isn't very insightful. How could it become insightful except for considering how the difficulty of the answer varies with the input? $\endgroup$
    – David Richerby
    Jul 27, 2018 at 14:01
  • $\begingroup$ @DavidRicherby, because what we're really interested in is some kind of derivation that shows that that string is the correct answer. So I suppose the question is about the computational complexity of the derivation which shows that a particular element of $\{yes,no\}$ is the correct answer to a decision problem. $\endgroup$
    – user56834
    Jul 27, 2018 at 14:56
  • $\begingroup$ OK but for a fixed instance, there's a fixed proof that yes or no is the correct answer and you still can't say much more without comparing the length of that proof to the lengths of the proofs for other instances. $\endgroup$
    – David Richerby
    Jul 27, 2018 at 14:58
  • $\begingroup$ @DavidRicherby, So you're saying that we cannot compare the computational complexity of the $8\times 8$ chess problem "instance", compared to that of the $3\times 3$ tic-tac-toe problem "instance"? clearly, one is harder than the other, in some meaningful sense. You seem to be saying: "there exists no meaningful way to assign a computational complexity metric to specific instances of a problem". That is a pretty strong statement. $\endgroup$
    – user56834
    Jul 27, 2018 at 15:01
  • 2
    $\begingroup$ You're looking for what is known as concrete complexity, of interest in cryptology. It's a replacement for complexity classes, which only make sense asymptotically. $\endgroup$
    – Yuval Filmus
    Jul 28, 2018 at 6:40

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the insightful answer! Intuitively, it still seems to me like there is a way to analyse this, without just giving a "amount of steps" required to solve the problem. I thought about this after reading this answer: cs.stackexchange.com/a/70711/56687. Look at the quote at the bottom: They say that one thing that makes chess difficult is the fact that the quantifiers alternate. I'm not saying this gives you an answer (they also alternate with tic-tac-toe). But it seems to me that analysis BROADLY LIKE THIS, might help put a metric/classification on problems that is... $\endgroup$
    – user56834
    Jul 28, 2018 at 6:23
  • $\begingroup$ independent from some kind of limiting process. But not by just giving a single number "amount of steps", but by giving a kind of classification on the basis of the "structure" of the computation that has to be done. $\endgroup$
    – user56834
    Jul 28, 2018 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.