Re: computer-go: NP-complete problems solved?

["Patrick G. Bridges" <bridges@xxxxxxxxxxxxxx>]

> 
> 
> On Mon, Oct 23, 2000 at 10:29:38AM -0700, Patrick G. Bridges wrote:
> 
> > Except according to a proof in Papadimitrou;s "Computational Complexity", 
> > Go is *not* NP, Go is PSPACE-complete, and PSPACE > NP.
> 
> Can you give us (non-mathematicians) some enlightenment about the
> differences?

Ah, I was wrong, if P = NP, then PSPACE=P=NP=coNP, etc... Interesting.

(I'm going to include a general computational complexity discussion here
for completeness. The PSPACE stuff is at the end, and I'm a systems weenie, not
a theory weenie, though I did have the required graduate theory course as part
of my doctoral work)

Problems in P can be solved in polynomial time (for size of problem n, they
can be solved in time a*n^c, where a and c are fixed constants for 
a given solution to the problem) on a deterministic turing machine(DTM), i.e. a 
regular computer.  Problems in P (sometimes called PTIME, meaining
polynomial time) are generally those thought of as tractable.

Problems in NP can be solved in polynomial time on a non-deterministic turing 
machine (NDTM). A non-deterministic turing machine, is (sort of) intuitively a 
computer that is allowed to "guess" between a constant number of choices, and
always guess correctly. One of the big theoretical conjectures in CS is 
P ?= NP. Clearly, those problems in P are a subset of those problems in NP.
Strangely enough, we can't prove whether there are problems in NP that are 
not in P. 

Problems that are NP-complete are conceptually the "hardest" problems in NP.
Any problem in NP can be reduced to one of these problems. For example, the 
travelling salesman problem (TSP) is NP-complete. This means if we can figure 
out how to solve TSP in deterministic polynomial time, then we can solve 
*every* problem NP problem in PTIME. Solving TSP, or any other NP-complete
problem in PTIME is sufficient to prove that P = NP, i.e., that every 
problem in class NP can be solved in polynomial time on a DTM.

So, P is a subset of NP. (P = NP is the question of whether P is a *proper* 
subset of NP.) Most people *believe* that it is, though noone has been able to
prove it. 

NP is a subset of other classes of problem. Here's one: PSPACE.
PSPACE are those problems that can be solved using a polynomial amount of 
storage. NP is clearly a subset of PSPACE, since in polynomial time, we can
only use polynomial storage.

Now, it turns out that NP is a proper subset of EXPTIME. There are problems 
that are in EXPTIME that are not in NP. It's not clear whether NP is a proper
subset of PSPACE. So, what people have done is outline the "hardest" problems
in PSPACE, namely PSPACE-complete problems. PSPACE-complete problems are those
that *every* other problem in PSPACE (and P and NP...) can be reduced to.
Go is one of these problems, where (n is size of the board.)

Now, it turns out that if P = NP, then P = NP = PSPACE, and Go should be
soluble in polynomial time. Of course, most people believe that P != NP, and
that PSPACE is a strict superset of P and NP, but no one has proved it yet.
The person we're talking about claims to have proven that P = NP by solving
a known NP-complete problem, the k-clique problem. 

-Patrick