3 ms·
I disagree. If P=NP, then we could very well start searching the space of polynomial algorithms until we find something that works and discard anything that is
by PartiallyTyped 6y ago
I disagree. If P=NP, then we could very well start searching the space of polynomial algorithms until we find something that works and discard anything that is not polynomial - which we can check apriori since the halting problem assumes we can't peak into the Turing machine, when in practice, we can.
- zests 6y agoEven knowing a polynomial algorithm for SAT would not have practical implications unless the algorithm has a reasonable run time. Matrix multiplication is a great example of a problem where the best known runtime complexity algorithms are not used even though for matrixes the size of the universe they would be faster.
- PartiallyTyped 6y agoI don't disagree, but it may also help in getting tighter bounds on algorithms, iirc Matrix Maltiplication doesn't have a tight Omega function. Also, finding such algorithms should significantly expand our capabilities by expanding our understanding.
- kongolongo 6y agoCouldn't we assume P=NP and try this anyways?
- PartiallyTyped 6y agoI mean, you could do that, but knowing it exists makes the search worthwhile.