|
|
|
|
|
|
by mihaild
3230 days ago
|
|
|
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. |
|
|