Re: Complexity Theory for Simpletons
 From: Bryan Olson <fakeaddress@xxxxxxxxxxx>
 Date: Thu, 30 Mar 2006 02:10:29 GMT
Woeginger Gerhard wrote:
[...]
We know several models of computation, in which P=NP holds.
I don't think that's really right. The model is part of the
definitions of P and NP. Either P=NP or it doesn't.
Certainly we know of models in which all languages in NP are
decidable in polytime, and that's enough to support your
case here.

Bryan
.
 FollowUps:
 Re: Complexity Theory for Simpletons
 From: tchow
 Re: Complexity Theory for Simpletons
 References:
 Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Googmeister
 Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard
 Re: Complexity Theory for Simpletons
 From: Craig Feinstein
 Re: Complexity Theory for Simpletons
 From: Woeginger Gerhard
 Complexity Theory for Simpletons
 Prev by Date: Linear Assignment Problem  Fast Algorithms?
 Next by Date: Re: Linear Assignment Problem  Fast Algorithms?
 Previous by thread: Re: Complexity Theory for Simpletons
 Next by thread: Re: Complexity Theory for Simpletons
 Index(es):
Relevant Pages
