[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> ***