4 ms·
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 gene
by Gehinnn 9y ago
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.
- kevinwang 9y agoCorrect me if I'm wrong, but enumerating all programs doesn't seem polytime
- mihaild 9y agoFormally, 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.