Re:My survey article on P vs. NP (2017)
by PartiallyTyped on Tuesday March 23, 2021 @11:10AM
(#26555950)
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.
[ Parent
| 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.
Re:My survey article on P vs. NP (2017)
by PartiallyTyped on Tuesday March 23, 2021 @07:23PM
(#26561650)
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.
Re:My survey article on P vs. NP (2017)
by kongolongo on Tuesday March 23, 2021 @01:34PM
(#26557717)
Couldn't we assume P=NP and try this anyways?
Re:My survey article on P vs. NP (2017)
by PartiallyTyped on Tuesday March 23, 2021 @07:16PM
(#26561589)
I mean, you could do that, but knowing it exists makes the search worthwhile.