Re:Throwing some light on NP-completeness and the P=NP problem
by philwelch on Wednesday June 03, 2009 @06:21PM
(#640580)
The "polynomial-time nondeterministic Turing machine" explanation has the following strengths:
1. It explains where the "N" in "NP" comes from and why.
2. For someone learning P and NP towards the end of an automata theory class, where nondeterminism and NFA-DFA transformations have already been introduced, it seems like a more elegant and meaningful development of the concept.
1. It explains where the "N" in "NP" comes from and why.
2. For someone learning P and NP towards the end of an automata theory class, where nondeterminism and NFA-DFA transformations have already been introduced, it seems like a more elegant and meaningful development of the concept.