3 ms·
What would really be interesting is someone finding a nonconstructive proof that P = NP. It would be quite a scramble to find the missing algorithms...
by scythe 16y ago
What would really be interesting is someone finding a nonconstructive proof that P = NP. It would be quite a scramble to find the missing algorithms...
- bdhe 16y agoWe already have algorithms for all NP problems, by Levin. See: http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-... No one knows whether it runs in polynomial time though! It runs in polytime if P=NP.
- deleted 16y ago[deleted]
- smallblacksun 16y ago"// "Polynomial-time" means it returns "yes" in polynomial time when // the answer should be "yes", and runs forever when it is "no"." That's an odd definition of polynomial time.
- bdhe 16y agoIt is just a technicality. If you know an upper bound on the running time you can simply run it for that many time steps and then return "no" if it doesn't halt by then (because it could never thereon answer "yes"). This only works with concrete upper bounds on running time (and not for general decidability).