3 ms·
As I understand it, the answer to P=NP or P!=NP does not give you the equations, it only tells you that there is an equation or not, so computer science would s
by thedevindevops 4y ago
As I understand it, the answer to P=NP or P!=NP does not give you the equations, it only tells you that there is an equation or not, so computer science would still have to work it out for each class of problem.
- dswilkerson 4y agoAll NP-complete problems can be transformed into each other using a polynomial time reduction. Therefore if you have a polynomial time solution to one, you immediately have a polynomial time solution to all of them. A hypothetical straightforward way to show P = NP would be to provide a polynomial time solution to one of the NP-complete problems, which, again, would therefore immediately solve them all in polynomial time. However, it is possible to prove that a method of solving a problem exists without exhibiting it. For example, some algorithms depend on expander graphs existing (such as multi-butterflies); initially expander graphs could be proven to exist (using Hungarian probabilistic techniques), but such a proof does not tell you an practical method for making an expander graph.
- thedevindevops 4y ago>All NP-complete problems can be transformed into each other using a polynomial time reduction. I did not know that, thanks for giving me something to read up on.