4 ms·
This is awesome. I will send him the program which runs every Turing machine simultaneously on his problem instance, and checks the output of each to see if it
by waqf 16y ago
This is awesome. I will send him the program which runs every Turing machine simultaneously on his problem instance, and checks the output of each to see if it is a correct solution.
If he manages to prove that my submission doesn't solve his problem in polynomial time, I'll refund his money, but I'll also send his proof on to the Clay Institute.
- swolchok 16y agoThere are infinitely many Turing machines.
- waqf 16y agoBut 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.
- swolchok 16y agoWhen do you accept? When do you reject? This is bogus, and can't even solve problems in P in polynomial time.
- waqf 16y agoYou 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_algorithms http://en.wikipedia.org/wiki/P%3DNP#Polynomial-time_algorith...