News for hackers. Stuff that matters.
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.

There are no comments on this comment yet.