Hacker News Reader

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.

View on HN

Even 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.

I 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.

Couldn't we assume P=NP and try this anyways?

I mean, you could do that, but knowing it exists makes the search worthwhile.

Reply on news.ycombinator.com