News for hackers. Stuff that matters.

A comment on A Solution of the P versus NP Problem?. Parent comment

Re:A Solution of the P versus NP Problem? by Gehinnn on Monday August 14, 2017 @07:34PM (#15014005)
Actually, we already know an algorithm that solves an NP complete problem in polynomial time iff P = NP. We can just enumerate all programs and ask them to generate witnesses. As we can decide whether a witness is valid and there is a program that always outputs a valid witness if P=NP, we can find that program within finite steps and the algorithm is correct.
[ Parent | on HN ]
Re:A Solution of the P versus NP Problem? by kevinwang on Monday August 14, 2017 @08:09PM (#15014231)
Correct me if I'm wrong, but enumerating all programs doesn't seem polytime
[ Parent | on HN ]
Re:A Solution of the P versus NP Problem? by mihaild on Monday August 14, 2017 @09:25PM (#15014597)
Formally, we run all possible programs in parallel: the 1st program runs for 1 step; the 1st and 2nd programs run for 1 additional step; programs 1-3 run for 1 additional step; ... After program stops, we check if its output is our witness. If there is program number K running in time f(n), then our program runs in time O(K * f^2(n) * [simulation time] * [check time]), which is polynomial if f is polynomial.
[ Parent | on HN ]