News for hackers. Stuff that matters.
Re:GetACoder.com: Solve P Vs NP by swolchok on Monday August 16, 2010 @11:04PM (#1610103)
There are infinitely many Turing machines.
Re:GetACoder.com: Solve P Vs NP by waqf on Tuesday August 17, 2010 @12:50AM (#1610303)
But there are only countably many Turing machines, and you only have to evaluate countably many steps of each, so all you need is a counting of NxN.
Re:GetACoder.com: Solve P Vs NP by swolchok on Thursday August 19, 2010 @12:58AM (#1616558)
When do you accept? When do you reject? This is bogus, and can't even solve problems in P in polynomial time.
Re:GetACoder.com: Solve P Vs NP by waqf on Thursday August 19, 2010 @01:20PM (#1617933)
You accept when you find a Turing machine that outputs something which turns out to be the polynomial-time verifiable certificate for the NP problem.

You never reject, because the requirement was only to accept in polynomial time. (If you prefer, you could reject in exponential time by exhaustive search, of course.)

For another description see here:

http://en.wikipedia.org/wiki/P%3DNP#Polynomial-time_algorith...