8 ms·

Introduction to P vs. NP

135 points by wesammikhail 4y ago

chippiewill 4y ago
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.
- TravHatesMe 4y ago
  I think it is a good layman's explanation, but I think the author could have explained NPC a bit better though, ie. mapping the inputs and outputs of a problem to a known NPC problem. Perhaps a brief overview of how NPC problems are proved to be NPC.
  - moefh 4y ago
    It suffers from the same problem a lot of layman's explanations have: it jumbles the explanation of what NP is. This is really annoying because it's so easy to do better: instead of saying (like the article does) "NP is a class of problems that are hard to solve yet easy to verify", you just have to say "NP is a class of problems that are easy to verify, no matter how hard they are to solve". With this small change it's much easier to see that P is inside NP, whereas with the original explanation, most people have to re-calibrate their understanding of what NP is when they learn that it actually does include P. It also makes it easy to see that "P vs NP" is just the question: "are there really any hard problems that are easy to verify, or is every problem like that easy and we just aren't very good at solving some of them?"
- shenman 4y ago
  Perhaps it depends on the audience. For a non-CS person, it's a pretty good introduction to solvability vs verifiability, and how seemingly similar math operations are quite asymmetric. I personally might use the example to convey the concept to non-CS people.
- ChancyChance 4y ago
  I thought it was helpful. Got a better link?
  - alberto_ol 4y ago
    This article for non-specialists is longer and more technical, but I found it interesting: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...
  - photochemsyn 4y ago
    This looks good: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf > "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”" "Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples: > "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features: (1) a finite but exponentially-large space of possible solutions; and (2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?) > "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel." The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.
jdlyga 4y ago
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."
- 4y ago
chx 4y ago
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.)
- andersentobias 4y ago
  You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?
  - quickthrower2 4y ago
    Profiling the code with different size inputs is sufficient
    - kaba0 4y ago
      I don’t know, I think knowing what algorithmic complexity is is really important, the problem is that all too many people just memorized that bubble sort is O(n^2) without understanding. Also, the reason why profiling is imo not good enough is that you really shouldn’t even try to write an implementation with a known-to-be “slow” algorithm at the designed input size. For that, understanding O-notation is essential.
- enriquto 4y ago
  Yes, the class P is huge. Calling problems in P "easy" is severely misguided. We have only barely scratched the surface of this class (linear and quadratic problems), but there is an infinitely deep ocean of problems below the surface that we cannot even imagine. It is illuminating to recall Knuth's view that probably P=NP, but it won't have any practical effect.
- madsbuch 4y ago
  Yes, I agree. Complexity theory is probably one of the least practical fields for software _engineers_, it can even work to a detriment, because you can discouraged to find solutions to problems. On the other hand, I have had great benefit from studying PL and semantics for software engineering. It taught me to write more readable and reliable code. (From a person who studied both as a part of his master)
xref 4y ago
> 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?
- harles 4y ago
  Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was completely impractical (I want to say something like N^6). It has an interesting history worth a read - it was also a big USSR contribution to the field, which there weren’t many of at the time. [0]: https://en.m.wikipedia.org/wiki/Ellipsoid_method https://en.m.wikipedia.org/wiki/Ellipsoid_method
  - xref 4y ago
    Oh wow thanks, this is definitely sending me down a Wikipedia rabbit hole; the Ellipsoid method was improved upon via Karmarkar’s algorithm in 1984. Also nicely illustrates that a problem which moves from NP to P can still be moved even further into P-territory _also_ Karmarkar’s algo appears to be an important law case on whether math can be copyrighted for people interested in that angle https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
- JohnKemeny 4y ago
  PRIMES, checking whether a number is a prime number or not. It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.
  - adgjlsfhk1 4y ago
    Primes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.
tromp 4y ago
> 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.
isaacfrond 4y ago
I recommend Computational Complexity: A Modern Approach readable, and covers all the topics
- genman 4y ago
  Highly recommended.
- alberto_ol 4y ago
  link to the free draft https://theory.cs.princeton.edu/complexity/book.pdf https://theory.cs.princeton.edu/complexity/book.pdf
bmacho 4y ago
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.
- zzzeek 4y ago
  the phrase "exponentially annoying" used non ironically given the context?
- rhn_mk1 4y ago
  > exponentially annoying. I see what you did there.
codeflo 4y ago
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.
- nvrspyx 4y ago
  Can't general problems be reduced to decision problems though?
  - bheadmaster 4y ago
    All I've seen pretty much can. Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.
    - Scea91 4y ago
      I am a bit rusty on this theory but isn't the N in your case related to the output size while you would need it to be related to input size instead?
      - bheadmaster 4y ago
        Depends on the problem, really. I've been out of school for half a decade now so I'm a little rusty too. I remember that the Traveling Salesman can be constructed as "is the minimum path less than N" in which N represents the solution, not the size.
  - thelastquestion 4y ago
    They can always be reduced, but sometimes with an unacceptably large (e.g., non-polynomial) increase in time complexity. These are the complexity classes of Function P (FP) and Function NP (FNP), which are the function problem extensions of the decision problem classes, and require finding the value, not just answering yes or no. A simple example of a decision problem in P but whose search problem is not known to be in FP: For a given integer x, “does there exist a non-trivial prime factor of x?” vs. “find a non-trivial prime factor of x”.
deleted 4y ago
[deleted]
friend_and_foe 4y ago
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.

135 points by wesammikhail 4y ago

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.

TravHatesMe 4y ago
I think it is a good layman's explanation, but I think the author could have explained NPC a bit better though, ie. mapping the inputs and outputs of a problem to a known NPC problem. Perhaps a brief overview of how NPC problems are proved to be NPC.
- moefh 4y ago
  It suffers from the same problem a lot of layman's explanations have: it jumbles the explanation of what NP is. This is really annoying because it's so easy to do better: instead of saying (like the article does) "NP is a class of problems that are hard to solve yet easy to verify", you just have to say "NP is a class of problems that are easy to verify, no matter how hard they are to solve". With this small change it's much easier to see that P is inside NP, whereas with the original explanation, most people have to re-calibrate their understanding of what NP is when they learn that it actually does include P. It also makes it easy to see that "P vs NP" is just the question: "are there really any hard problems that are easy to verify, or is every problem like that easy and we just aren't very good at solving some of them?"
shenman 4y ago
Perhaps it depends on the audience. For a non-CS person, it's a pretty good introduction to solvability vs verifiability, and how seemingly similar math operations are quite asymmetric. I personally might use the example to convey the concept to non-CS people.
ChancyChance 4y ago
I thought it was helpful. Got a better link?
- alberto_ol 4y ago
  This article for non-specialists is longer and more technical, but I found it interesting: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW09.pdf https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...
- photochemsyn 4y ago
  This looks good: https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf > "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”" "Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples: > "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features: (1) a finite but exponentially-large space of possible solutions; and (2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?) > "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel." The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.

jdlyga 4y ago

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."

4y ago

chx 4y ago

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.)

andersentobias 4y ago
You don't need to involve a P vs NP discussion at all if you want to have a practical discussion to begin with. Big-Oh is sufficient?
- quickthrower2 4y ago
  Profiling the code with different size inputs is sufficient
  - kaba0 4y ago
    I don’t know, I think knowing what algorithmic complexity is is really important, the problem is that all too many people just memorized that bubble sort is O(n^2) without understanding. Also, the reason why profiling is imo not good enough is that you really shouldn’t even try to write an implementation with a known-to-be “slow” algorithm at the designed input size. For that, understanding O-notation is essential.
enriquto 4y ago
Yes, the class P is huge. Calling problems in P "easy" is severely misguided. We have only barely scratched the surface of this class (linear and quadratic problems), but there is an infinitely deep ocean of problems below the surface that we cannot even imagine. It is illuminating to recall Knuth's view that probably P=NP, but it won't have any practical effect.
madsbuch 4y ago
Yes, I agree. Complexity theory is probably one of the least practical fields for software _engineers_, it can even work to a detriment, because you can discouraged to find solutions to problems. On the other hand, I have had great benefit from studying PL and semantics for software engineering. It taught me to write more readable and reliable code. (From a person who studied both as a part of his master)

xref 4y ago

> 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?

harles 4y ago
Not a recent example, but the Ellipsoid Method[0] is a famous example of this. It took a class of problems (Linear Programs) from NP to P in 1979 but was completely impractical (I want to say something like N^6). It has an interesting history worth a read - it was also a big USSR contribution to the field, which there weren’t many of at the time. [0]: https://en.m.wikipedia.org/wiki/Ellipsoid_method https://en.m.wikipedia.org/wiki/Ellipsoid_method
- xref 4y ago
  Oh wow thanks, this is definitely sending me down a Wikipedia rabbit hole; the Ellipsoid method was improved upon via Karmarkar’s algorithm in 1984. Also nicely illustrates that a problem which moves from NP to P can still be moved even further into P-territory _also_ Karmarkar’s algo appears to be an important law case on whether math can be copyrighted for people interested in that angle https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
JohnKemeny 4y ago
PRIMES, checking whether a number is a prime number or not. It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.
- adgjlsfhk1 4y ago
  Primes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.

tromp 4y ago

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

isaacfrond 4y ago

I recommend Computational Complexity: A Modern Approach readable, and covers all the topics

genman 4y ago
Highly recommended.
alberto_ol 4y ago
link to the free draft https://theory.cs.princeton.edu/complexity/book.pdf https://theory.cs.princeton.edu/complexity/book.pdf

bmacho 4y ago

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.

zzzeek 4y ago
the phrase "exponentially annoying" used non ironically given the context?
rhn_mk1 4y ago
> exponentially annoying. I see what you did there.

codeflo 4y ago

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.

nvrspyx 4y ago
Can't general problems be reduced to decision problems though?
- bheadmaster 4y ago
  All I've seen pretty much can. Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.
  - Scea91 4y ago
    I am a bit rusty on this theory but isn't the N in your case related to the output size while you would need it to be related to input size instead?
    - bheadmaster 4y ago
      Depends on the problem, really. I've been out of school for half a decade now so I'm a little rusty too. I remember that the Traveling Salesman can be constructed as "is the minimum path less than N" in which N represents the solution, not the size.
- thelastquestion 4y ago
  They can always be reduced, but sometimes with an unacceptably large (e.g., non-polynomial) increase in time complexity. These are the complexity classes of Function P (FP) and Function NP (FNP), which are the function problem extensions of the decision problem classes, and require finding the value, not just answering yes or no. A simple example of a decision problem in P but whose search problem is not known to be in FP: For a given integer x, “does there exist a non-trivial prime factor of x?” vs. “find a non-trivial prime factor of x”.

deleted 4y ago

[deleted]

friend_and_foe 4y ago

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.