Re: Complexity Theory for Simpletons



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 poly-time, and that's enough to support your
case here.


--
--Bryan
.