Re: [computer-go] Search = Bad!

[Maarten Mariën <maarten.marien@xxxxxxxxx>]

> For go, a shortcut formula is even less likely, since its PSPACE completeness
> implies that any fast (subexponential) algorithm for go would translate to
> a fast algorithm for *any* problem whatsoever solvable in polynomial space.

This has come up before, but I think it worthwhile to repeat.
Properties such as NP-completeness or PSPACE completeness are
properties about decision problems.

(from www.complexityzoo.com)
====
decision problem: A problem for which the desired answer is a single
bit (1 or 0, yes or no). For simplicity, theorists often restrict
themselves to talking about decision problems.

problem: A function from inputs to outputs, which we want an algorithm
to compute. A crossword puzzle is not a problem; it's an instance. The
set of all crossword puzzles is a problem.
====

The PSPACE-completeness result in go is (AFAIK) related to
ladder-reading, which is a problem in the sense described above. 19x19
go is a problem instance, not a problem.

Maarten.
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/