HACKER Q&A
📣 amichail

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


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


  👤 Someone Accepted Answer ✓
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 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.


👤 thedevindevops
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.

👤 nabla9
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.


👤 PaulHoule
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.