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