News for hackers. Stuff that matters.
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.
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.
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.