Re:My survey article on P vs. NP (2017)
by zests on Tuesday March 23, 2021 @11:42AM
(#26556340)
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.
[ Parent
| on HN ]
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.