3 ms·
Hmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
by sdenton4 9y ago
Hmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
- murbard2 9y agoYes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant. Of course, that constant is astronomically unpractical.
- ufo 9y agoI like the term "Galactic Algorithm" for these algorithms with unpractical constants. https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/ https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...