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

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

>>>>> "PGB" == Patrick G Bridges <bridges@xxxxxxxxxxxxxxxxx> writes:

    PGB> The corollary to THeorem 17.9 on p. 427 of Papademitrou's
    PGB> "Computational Complexity" that states:

    PGB> "If P = NP, or even if NP = coNP, the polynomial hierarchy
    PGB> (i.e. the hierarchy from P to PSPACE) collapses to the first
    PGB> level."

    PGB> Am I misunderstanding the meaning of this statement?


I am, it turns out. Herve pointed out that the the polynomial
hierarchy (PH) is a subset of PSPACE, but it's not known whether PH is
a a strict subset of PSPACE or not. I.E., we know PH <= PSPACE, but
don't know that PH = PSPACE.  The PH collapsing if P=NP (I'm still
skeptical) may not have any affect on PSPACE-complete problems like
Go.

Thanks for the correction, Herve.

-Patrick

-- 
*** Patrick G. Bridges  	     	bridges@xxxxxxxxxxxxxxxxx ***
***                #include <std/disclaimer.h>		       ***