3 ms·

Ask HN: Would theoretical computer science survive the resolution of P vs. NP?

3 points by amichail 4y ago

Maybe the answer would depend on whether P=NP or P!=NP?

PaulHoule 4y ago
The other day I was reading Knuth’s fascile on satisfiability where he says his hunch is that P = NP but the algorithm might be outside our capacity to understand or implement.
Someone 4y ago
Why on earth would you think it wouldn’t? The field is much, much broader than that. https://en.wikipedia.org/wiki/Theoretical_computer_science https://en.wikipedia.org/wiki/Theoretical_computer_science quotes The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT): TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
nabla9 4y ago
Why wouldn't it? 1) If P = NP and and the bounding polynomial is immensely huge, it would be somewhat disappointing, but interesting nonetheless. 2) if P = NP and there is efficient algorithm, it would be amazing. There are problems harder that NP-complete problems. 3) P != NP, then nothing would change.
- dswilkerson 4y ago
  This answer is basically correct.
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 ago
  All 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.

3 points by amichail 4y ago

Maybe the answer would depend on whether P=NP or P!=NP?

The other day I was reading Knuth’s fascile on satisfiability where he says his hunch is that P = NP but the algorithm might be outside our capacity to understand or implement.

Someone 4y ago

Why on earth would you think it wouldn’t? The field is much, much broader than that. https://en.wikipedia.org/wiki/Theoretical_computer_science https://en.wikipedia.org/wiki/Theoretical_computer_science quotes The ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT): TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

nabla9 4y ago

Why wouldn't it? 1) If P = NP and and the bounding polynomial is immensely huge, it would be somewhat disappointing, but interesting nonetheless. 2) if P = NP and there is efficient algorithm, it would be amazing. There are problems harder that NP-complete problems. 3) P != NP, then nothing would change.

dswilkerson 4y ago
This answer is basically correct.

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 ago
All 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.