from Hacker News

Introduction to P vs. NP

by wesammikhail on 3/23/23, 11:19 PM with 39 comments

• by tromp on 3/24/23, 8:13 AM

  > P is a class of problems that are easy to solve and easy to verify.

  > NP, on the other hand, is a class of problems that are hard to solve yet easy to verify.

  The latter description is not quite correct, as NP includes P. So not all problems in NP are hard to solve. Similarly with EXP.

  The class of problems that are hard to solve yet easy to verify, is exactly NP\P, which we assume (but cannot prove) is non-empty.

• by chx on 3/24/23, 6:13 AM

  One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one.

  This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate number of atoms in the observable universe.)

• by chippiewill on 3/24/23, 2:38 AM

  I feel like this is a pretty bad introduction to P vs NP., no? It doesn't ever actually even begin to explain what P and NP are, only what their vague properties are.

• by codeflo on 3/24/23, 10:48 AM

  I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.

• by friend_and_foe on 3/25/23, 7:02 AM

  Sudoku coming up, I was actually rolling around in my head this idea of encoding information in unsolved sudoku puzzles as a form of compression, and wondering how much you can get out of it, how much of it needs to be error correction and the like. Never did any math on it, it's one of those things I think about and "will sit down and mess with later" supposedly but I doubt there will be anything novel or more efficient to come of it that's not directly translatable into existing compression.

• by xref on 3/24/23, 6:13 AM

  > Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain

  Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?

• by isaacfrond on 3/24/23, 8:33 AM

  I recommend

  Computational Complexity: A Modern Approach

  readable, and covers all the topics

• by bmacho on 3/24/23, 10:47 AM

  For the laymans out there: pls don't just randomly use words like NP-complete or NP-hard or such, when you only know that a problem is "hard", or you don't see a trivial solution. It's exponentially annoying.

• by jdlyga on 3/24/23, 3:11 AM

  I like GPT-4's explanation of P vs NP.

  Prompt:

  "Give me good computer science arguments for why P = NP and why P != NP"

  Response:

  "The P vs. NP problem is a major open question in computer science, which asks whether problems whose solutions can be quickly verified by a computer can also be quickly solved by a computer. Both sides of the argument have been extensively debated, but the problem remains unsolved. Here are some arguments for both possibilities:

  Arguments for P = NP:

  Lack of counterexamples: Despite extensive research, no concrete counterexample has been found to definitively prove that P != NP. This lack of evidence may suggest that P = NP could still be true.

  Potential algorithmic breakthroughs: If P = NP, this implies that a polynomial-time algorithm exists for every problem in NP, even though such algorithms may not be known yet. There is always the possibility that new algorithmic techniques or breakthroughs could be discovered, leading to polynomial-time solutions for NP problems.

  Simplicity and symmetry: From a theoretical perspective, some argue that P = NP is a more elegant and symmetric outcome, as it would mean all problems that can be verified in polynomial time can also be solved in polynomial time.

  Arguments for P != NP:

  Exponential lower bounds: Some computational problems have proven exponential lower bounds, indicating that these problems are fundamentally difficult to solve. While these problems may not be in NP, they provide evidence that not all problems can be solved efficiently.

  The lack of efficient algorithms: Despite extensive research and many attempts, no efficient (i.e., polynomial-time) algorithms have been found for any of the NP-complete problems, which are among the hardest problems in NP. This suggests that P and NP might indeed be separate complexity classes.

  The existence of NP-complete problems: NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time. They are considered the hardest problems in NP. The existence of such problems, and the lack of polynomial-time algorithms for them, supports the belief that P != NP.

  Cryptography: Modern cryptography relies on the assumption that certain problems are hard to solve, such as factoring large numbers. If P = NP, then these cryptographic schemes would become insecure, as the difficult problems on which they are based could be solved efficiently. The widespread use and success of cryptography provide some evidence that P != NP.

  It is important to note that these arguments are speculative, and no definitive proof has been found for either side of the debate. The P vs. NP problem remains a significant open question in computer science."