[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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



>>>>> "HF" == Herve Fournier <hfournie@xxxxxxxxxxxxxxxxx> writes:

    HF> I would like to correct a few things that have been said about
    HF> complexity.  In fact P included in NP included in PSPACE
    HF> included in EXPTIME.  The only inclusion known to be strict is
    HF> P strictly included in EXPTIME.  There is no known theorem
    HF> like P=NP => P=PSPACE as stated in a previous post. But
    HF> P=PSPACE => P=NP of course.

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

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

Am I misunderstanding the meaning of this statement?

-Patrick Bridges

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