Re:An Argument for P=NP (2005) [pdf]
by theseoafs on Monday August 17, 2015 @02:48PM
(#10075231)
> Can you restrict it to "the yes/no answer provided by whatever that Turing machine runs, provided that it runs in polynomial time"?
Yes, essentially. You stop the simulation after T(n) steps, where T is a polynomial function that depends on the simulation, and reject the input if you haven't accepted by that point. It's clearly in NP as a result.
Yes, essentially. You stop the simulation after T(n) steps, where T is a polynomial function that depends on the simulation, and reject the input if you haven't accepted by that point. It's clearly in NP as a result.