14 ms·

P vs. NP and the Computational Complexity Zoo (2014) [video]

190 points by luu 11y ago

yoha 11y ago
Reddit's thread: https://www.reddit.com/r/programming/comments/372634/the_n_vs_np_problem_explained/ https://www.reddit.com/r/programming/comments/372634/the_n_v... The video is very well structured and goes from very basic explanations of the concept of complexity up to the different classes of complexities.
- mapmap 11y ago
  Thanks for the link. Found this great comment: My expectation, however, is that either P!=NP or if it isn't, we will probably find out because some day, some guy wanted his program to run a little faster and he just happens to solve A NP-complete problem in polynomial time, therefore collapsing NP into P (remember, solving one of them solves all of them). Who knows, maybe the source code for some random Indie game someone programmed in his basement already contains the solution and nobody has noticed, a bit like back in the day with quakes "fast-inverse square root", which was so great it's now integral part of graphics computing. And we only noticed because the water looked so great. https://www.reddit.com/r/programming/comments/372634/the_n_vs_np_problem_explained/crj9h4d https://www.reddit.com/r/programming/comments/372634/the_n_v...
DanAndersen 11y ago
I definitely got a sense of mathematical awe out of that. Thanks for sharing. I'm always impressed when I see someone who can communicate ideas, especially complex scientific concepts, clearly and effectively, using analogies in a proper way that doesn't just overwhelm the viewer (as a lot of popsci stuff does). It's a talent I know that I need to work on; as a fledgling academic attempting to write papers clearly I struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?
- nsnick 11y ago
  Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (correct me if I am wrong) a problem that can only be solved in factorial time on a Deterministic Turing Machine for example cannot be part of the class NP. He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest. https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en https://www.ibm.com/developerworks/community/blogs/jfp/entry...
  - CJefferson 11y ago
    There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a decision problem, by saying "is there a path of length k or less?". Then it is in NP-complete
    - nsnick 11y ago
      So yeah in the video, traveling salesman should not have been included in NP
    - ColinWright 11y ago
      > There is no debate, plain travelling salesman > is defiantly not known to be NP-complete. Actually, there is no debate, plain TSP is specifically not NP-complete and cannot be, because it's not a decision problem. So it's not just, as you say, "not known to be" but instead is "known not to be". However, by using binary search you can convert a decision version of TSP into the optimisation version in polynomial time. In this sense it is perfectly reasonable to refer to TSP as being NP-Complete. I agree completely that these sorts of differences actually matter when dealing with the technicalities, but in practice it makes sense not to worry too much when trying to explain the broader concepts.
z3t4 11y ago
That video helped a lot, but I'm still struggling to understand what the N=NP question means and how to prove it. I think that all problems with a set definition for "solved" is solvable as in "P". For example, the rubik's cube is solved if all sides have a solid color. And is thus a "P".
- Ar-Curunir 11y ago
  NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.
  - z3t4 11y ago
    So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming
    - Ar-Curunir 11y ago
      Well no, every problem in P is in NP trivially. To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.
      - nsnick 11y ago
        To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
        Ar-Curunir 11y ago
        No, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.
deleted 11y ago
[deleted]
natehouk 11y ago
P=NP!=MAD
omot 11y ago
Is Google search solving a np complete/hard problem relatively quickly? Is that how you become a billion dollar company?
deleted 11y ago
[deleted]
enupten 11y ago
I found this paper to be an excellent discussion on the implications that Physics has on the complexity question, http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf
rrodriguez89 11y ago
Remember quantum computing ? a lot of NP problems will become P
- Ar-Curunir 11y ago
  No, they'll become a part of BQP (or rather are already). P is defined as the class of problems decidable in polynomial time on a classical Turing machine. P doesn't change with the advent of quantum computers. Also it is suspected that BQP \not \subset NP, i.e. there are problems in BQP that might not be in NP.
  - eru 11y ago
    And almost certainly, NP \not \subset BQP. In fact, there are only a few problems found so far where quantum computing gives a speedup compared to classical computers.
Zezima 11y ago
Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.
- truncate 11y ago
  I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it. http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358 http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...
- justifier 11y ago
  i talk about karp's paper: reducibility among combinatorial problems(i); in another thread and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21 (i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00031000000000000000 http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...
pjungwir 11y ago
"Simplicity is the final achievement" -- Chopin, according to the video. After a bunch of Googling the only source I can find for this is a 2007 religious apologetics book with no Amazon reviews. I can't even find a French version of the quote. Anyone know if it's legitimate? And a more interesting question: if no one has ever even reviewed this book, how is it all over the Internet as the source of this quote? EDIT: Oops, looks like it is not religious apologetics. Still, I'm curious how a (presumably manufactured) quote like this spreads from such an obscure source.
Ocerge 11y ago
This definitely stirred up some of the dust in my head that has settled since I took Algorithms in college. Specifically, I forgot about how different the world would be if P is actually NP. It's interesting to think about, kind of in the same vein as trying to comprehend the size of the universe.
- justifier 11y ago
  i'm trying to envision a world where P and NP actually diverge, the universe is a fractal
- komodekork 11y ago
  How would it be any different? It is what it is...
graycat 11y ago
To start, yes, I do like the question of P versus NP and regard it as a very important research question. My reaction to the video lecture: Wow. Amazing. Gee whiz. P versus NP. What a biggie! Or is it? There does seem to be a little, tiny, itsy, bitsy point where the lecture went off the track: The lecture gave a big list of some of the amazing things we could do if we could prove that P = NP. Some of the items on that list were protein folding (to cure cancer) and scheduling. Right? Not so much: If someone has an important problem in scheduling, protein folding or any of the NP-complete problems, bring forward that actual, specific, instance of the real problem. Why? Because there's no proof and little evidence that finding a solution will be too difficult for "current computers". To this claim I can hear the complaint now: "But, but, but, the problems in NP-complete are too difficult to solve for current computers because as the problem size increases, the best known algorithms have running time that grows as an exponential in the size of the problem, and exponential growth limits us to problem instances of just small down to tiny size." Yup, can hear that complaint. Good news, guys: The complaint is false and does not correctly explain the challenge of NP-complete. E.g,, 0-1 integer linear programming is in NP-complete, but I can write down, as fast as I can type, such problems about as big as you please that I, or anyone, can solve quickly just by simple inspection. It's true. E.g., for any positive integer n, consider the 0-1 integer linear programming problem max z = 1 * x1 + 2 * x2 + ... + n * xn subject to x1 + x2 + ... + xn = 1 x1, x2, ..., xn = 0 or 1 So, the error in the complaint is that actually the question of P versus NP has to do with worst case instances of the problems. But practical instances are not all worst case, and for many of the practical instances we can get solutions. So, for any particular actual, specific, instance of a real problem, bring it forward -- you might be able to get a solution. And, wait, there's more! For a problem like scheduling, mostly what is desired is just to save money in the actual operations, say, airlines where we need to schedule the planes for the planned flights, the crews, and maintenance for the planes. Since the planes do fly, tough to convince me that the scheduling is impossible. So, if spending $200 million a month on operations, an optimal schedule could save $20 million, can find a schedule that is approximately optimal and saves all but the last $100,000, then take the $19,900,000 savings and be happy. The claim "we want to show that P = NP so that we can solve all these important problems" has been going on since the cartoon early in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness'. where the mathematician stood before the business executive and admitted that he could not solve the executive's problem but neither could any of the mathematicians in a long line. Likely nonsense: The mathematician was likely just looking for a long term job and actually not at all interested in solving the executive's problem. Why? Because there was no indication that the executive's problem was large and worst case and needed an exactly optimal solution instead of a nearly optimal solution. The executive's problem might have been relatively easy to solve, with a nearly optimal solution and maybe with an exactly optimal solution. Indeed, the book was from Bell Labs where one of their interests was network design. Well, since the phones did work, somehow Bell did find feasible solutions. Optimal? Maybe not. So, what was "the executive's problem" that was in NP-complete and "too difficult to solve?". Maybe he just wanted to design a telecommunications network to have the needed performance and reliability and, otherwise, get the cost down as much as possible or nearly so. Finding an algorithm that shows that P = NP is very likely a significantly different problem, not his problem, and not necessary for his problem. This erroneous belief that all large instances of problems in NP-complete are too difficult to solve is too common: E.g., once I got a problem in allocation of marketing resources. The instance was 0-1 integer linear programming with 40,000 constraints and 600,000 variables. I thought for a day or so, typed in some software, did some Lagrangian relaxation, and in 905 seconds on a 90 MHz PC got a feasible solution guaranteed to be within 0.025% of optimality. Close enough for gumment work! Then, later, as I was considering network design for the Internet, I got an interview at a network design startup in Texas and mentioned the problem with the 600,000 variables. Well, the whole technical staff was on the other side of the table, had heard the horror stories about NP-complete in college, and concluded to a person that I was claiming to have done the impossible and had to be lying. I left without a job offer, and they soon went out of business. By the way, Mother Nature does protein folding, right? Hmm ....
MrBuddyCasino 11y ago
Lets say I want to solve a problem, but I have no idea if it is solvable in polynomial time. Is there a website or a book where I can look that up?
- eru 11y ago
  Complexity Zoo.
infogulch 11y ago
What about the problem of a solution to P and NP being ambiguous for practical uses? I read this argument somewhere, but can't find it now: Case 1, it's proved that P = NP, and the complexity of solving an NP problem is N^1000. Case 2, it's proved that P != NP, and the complexity of solving an NP problem is N^log log log log N. In both cases, the result is technically correct (case 1 is polynomial, case 2 is exponential), but from a practical standpoint this proof that P != NP is much more world changing than this proof that P = NP. For example, you'd have to have a problem size that's measured in hundreds of digits before even getting to N^3!
- eru 11y ago
  In practice we find that algorithms in P usually have small exponents. And thus P is a good shorthand for tractable. If case 2 happens, we'll have to change our shorthand to what we actually care about: tractability. Similar arguments apply to case 1. (We know quite a bit about how a proof of NP ?= P could _not_ look like, because people already proved that certain strategies for a proof don't work. I am not sure if we can already rule out N^log log log log N, but it wouldn't surprise me.)
  - dllthomas 11y ago
    "In practice we find that algorithms in P usually have small exponents." We find that algorithms we have identified in P usually have small exponents. This may simply be selection bias, if we are poor at coming up with n^4+ algorithms.
  - infogulch 11y ago
    So, "P" and "NP" are just one possible set of precise definitions for "tractable" and "intractable", and so far they have aligned nicely so they can be used interchangeably (and it's unlikely to change much).
    - eru 11y ago
      Actually, NP isn't too intractable in practice. We are routinely solving huge instances of NP hard problems these days. There are problems that we hope are hard in the average case. Like breaking cryptography.
swehner 11y ago
The video is misleading when it spreads the idea that "polynomial time" equals "practical," or "fast". It's nice and simple to talk like that, but I don't think it's particularly useful or helpful. For example, there is a linear time algorithm for deciding whether two planar graphs are isomorphic (Hopcroft,Wong 1974). But the constant of the asymptotic time bound of their algorithm so large that it was not useful or practical (see end of abstract, http://dl.acm.org/citation.cfm?id=803896 http://dl.acm.org/citation.cfm?id=803896) Only in 2004 did Kukluk, Holder, Cook publish a quadratic time algorithm, "suitable for practical implementation." http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf More such examples are listed at "Polynomial-time algorithms with huge exponent/constant," http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...
- peeters 11y ago
  I think the video addresses it in a fair and approachable manner. It makes it clear that the value is in scaling algorithms to larger inputs, and even shows so in a graph. When dealing with unbounded scaling, the constants typically do not matter.
mottalrd 11y ago
Amazing, thank you for sharing

190 points by luu 11y ago

yoha 11y ago

Reddit's thread: https://www.reddit.com/r/programming/comments/372634/the_n_vs_np_problem_explained/ https://www.reddit.com/r/programming/comments/372634/the_n_v... The video is very well structured and goes from very basic explanations of the concept of complexity up to the different classes of complexities.

mapmap 11y ago
Thanks for the link. Found this great comment: My expectation, however, is that either P!=NP or if it isn't, we will probably find out because some day, some guy wanted his program to run a little faster and he just happens to solve A NP-complete problem in polynomial time, therefore collapsing NP into P (remember, solving one of them solves all of them). Who knows, maybe the source code for some random Indie game someone programmed in his basement already contains the solution and nobody has noticed, a bit like back in the day with quakes "fast-inverse square root", which was so great it's now integral part of graphics computing. And we only noticed because the water looked so great. https://www.reddit.com/r/programming/comments/372634/the_n_vs_np_problem_explained/crj9h4d https://www.reddit.com/r/programming/comments/372634/the_n_v...

DanAndersen 11y ago

I definitely got a sense of mathematical awe out of that. Thanks for sharing. I'm always impressed when I see someone who can communicate ideas, especially complex scientific concepts, clearly and effectively, using analogies in a proper way that doesn't just overwhelm the viewer (as a lot of popsci stuff does). It's a talent I know that I need to work on; as a fledgling academic attempting to write papers clearly I struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?

nsnick 11y ago
Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (correct me if I am wrong) a problem that can only be solved in factorial time on a Deterministic Turing Machine for example cannot be part of the class NP. He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest. https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en https://www.ibm.com/developerworks/community/blogs/jfp/entry...
- CJefferson 11y ago
  There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a decision problem, by saying "is there a path of length k or less?". Then it is in NP-complete
  - nsnick 11y ago
    So yeah in the video, traveling salesman should not have been included in NP
  - ColinWright 11y ago
    > There is no debate, plain travelling salesman > is defiantly not known to be NP-complete. Actually, there is no debate, plain TSP is specifically not NP-complete and cannot be, because it's not a decision problem. So it's not just, as you say, "not known to be" but instead is "known not to be". However, by using binary search you can convert a decision version of TSP into the optimisation version in polynomial time. In this sense it is perfectly reasonable to refer to TSP as being NP-Complete. I agree completely that these sorts of differences actually matter when dealing with the technicalities, but in practice it makes sense not to worry too much when trying to explain the broader concepts.

z3t4 11y ago

That video helped a lot, but I'm still struggling to understand what the N=NP question means and how to prove it. I think that all problems with a set definition for "solved" is solvable as in "P". For example, the rubik's cube is solved if all sides have a solid color. And is thus a "P".

Ar-Curunir 11y ago
NP = Set of problems for which candidate solutions can be checked for correctness in polynomial time in the length of the input. P = Set of problems for which we can find a solution in polynomial time in the length of the input. Clearly, P \subseteq NP. Proving P = NP would require proving NP \subseteq P, something which most people would believe to be a) highly unlikely b) difficult.
- z3t4 11y ago
  So basically I have to find a problem that categories as P but not NP!? Kinda like the Planck constant in quantum theory. f(2) = 4, f(3) = ? /brainstorming
  - Ar-Curunir 11y ago
    Well no, every problem in P is in NP trivially. To prove P = NP, you would have to prove that one of the many NP-Complete problems has a polytime algorithm. Well that's not the only way to prove P = NP, but that's one approach.
    - nsnick 11y ago
      To prove that P does not equal NP you would have to prove that a problem thought to be NP Complete was in fact NP Intermediate. That is, the problem meets the conditions of NP, but NP Complete problems cannot be reduced to it.
      - Ar-Curunir 11y ago
        No, not really. There are many NP-Complete problems, and there are many NP problems that are thought to be neither NPC nor in P. In fact, if P != NP, there are infinitely many such problems. So proving P != NP could proceed by finding some problem in NP that is not also in P.

deleted 11y ago

[deleted]

natehouk 11y ago

P=NP!=MAD

omot 11y ago

Is Google search solving a np complete/hard problem relatively quickly? Is that how you become a billion dollar company?

deleted 11y ago

[deleted]

enupten 11y ago

I found this paper to be an excellent discussion on the implications that Physics has on the complexity question, http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf

rrodriguez89 11y ago

Remember quantum computing ? a lot of NP problems will become P

Ar-Curunir 11y ago
No, they'll become a part of BQP (or rather are already). P is defined as the class of problems decidable in polynomial time on a classical Turing machine. P doesn't change with the advent of quantum computers. Also it is suspected that BQP \not \subset NP, i.e. there are problems in BQP that might not be in NP.
- eru 11y ago
  And almost certainly, NP \not \subset BQP. In fact, there are only a few problems found so far where quantum computing gives a speedup compared to classical computers.

Zezima 11y ago

Can anyone suggest further reading on the topic? Anything from Computational Papers on P vs. NP to "Computation Complexity Classes for Dummies" is fine with me.

truncate 11y ago
I studied this topic mainly from Algorithms text by Kleinberg/Tardos[1]. Like everything else, if you interested in proving problems NPC, read few examples from book and practice some on your own. Proving problems NPC of some common problems isn't very hard once you get hang of it. http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358 http://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321...
justifier 11y ago
i talk about karp's paper: reducibility among combinatorial problems(i); in another thread and i found this integer programming tutorial comprehensive in offering practical applications of the desired algorithm(ii) do any of these examples explain the problem best for you? can you write a program that will solve this question for you? now change the values of the variables, increase the number of variables does your algorithm still work on these other inputs? can you rewrite the algorithm to give the correct answers for these other inputs? can you develop enough coverage to prove all possible inputs return correct values? if your coverage is substantial, seemingly complete, can you write against your algorithm to find inputs that will still require you to further develop the algorithm? for me, i felt i was able to follow the explanation for how the author found the answer and through that was able to start to see the shape of the coverage necessary to accommodate such a problem (iii) this specific tutorial is on integer programming.. one of karp's 21, and through reduction on our understanding of 0-1 integer programming we can understand all of the other 21 (i) http://www.cs.berkeley.edu/~luca/cs172/karp.pdf http://www.cs.berkeley.edu/~luca/cs172/karp.pdf (ii) http://mat.gsia.cmu.edu/orclass/integer/integer.html http://mat.gsia.cmu.edu/orclass/integer/integer.html (iii) http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00031000000000000000 http://mat.gsia.cmu.edu/orclass/integer/node4.html#SECTION00...

pjungwir 11y ago

"Simplicity is the final achievement" -- Chopin, according to the video. After a bunch of Googling the only source I can find for this is a 2007 religious apologetics book with no Amazon reviews. I can't even find a French version of the quote. Anyone know if it's legitimate? And a more interesting question: if no one has ever even reviewed this book, how is it all over the Internet as the source of this quote? EDIT: Oops, looks like it is not religious apologetics. Still, I'm curious how a (presumably manufactured) quote like this spreads from such an obscure source.

Ocerge 11y ago

This definitely stirred up some of the dust in my head that has settled since I took Algorithms in college. Specifically, I forgot about how different the world would be if P is actually NP. It's interesting to think about, kind of in the same vein as trying to comprehend the size of the universe.

justifier 11y ago
i'm trying to envision a world where P and NP actually diverge, the universe is a fractal
komodekork 11y ago
How would it be any different? It is what it is...

graycat 11y ago

To start, yes, I do like the question of P versus NP and regard it as a very important research question. My reaction to the video lecture: Wow. Amazing. Gee whiz. P versus NP. What a biggie! Or is it? There does seem to be a little, tiny, itsy, bitsy point where the lecture went off the track: The lecture gave a big list of some of the amazing things we could do if we could prove that P = NP. Some of the items on that list were protein folding (to cure cancer) and scheduling. Right? Not so much: If someone has an important problem in scheduling, protein folding or any of the NP-complete problems, bring forward that actual, specific, instance of the real problem. Why? Because there's no proof and little evidence that finding a solution will be too difficult for "current computers". To this claim I can hear the complaint now: "But, but, but, the problems in NP-complete are too difficult to solve for current computers because as the problem size increases, the best known algorithms have running time that grows as an exponential in the size of the problem, and exponential growth limits us to problem instances of just small down to tiny size." Yup, can hear that complaint. Good news, guys: The complaint is false and does not correctly explain the challenge of NP-complete. E.g,, 0-1 integer linear programming is in NP-complete, but I can write down, as fast as I can type, such problems about as big as you please that I, or anyone, can solve quickly just by simple inspection. It's true. E.g., for any positive integer n, consider the 0-1 integer linear programming problem max z = 1 * x1 + 2 * x2 + ... + n * xn subject to x1 + x2 + ... + xn = 1 x1, x2, ..., xn = 0 or 1 So, the error in the complaint is that actually the question of P versus NP has to do with worst case instances of the problems. But practical instances are not all worst case, and for many of the practical instances we can get solutions. So, for any particular actual, specific, instance of a real problem, bring it forward -- you might be able to get a solution. And, wait, there's more! For a problem like scheduling, mostly what is desired is just to save money in the actual operations, say, airlines where we need to schedule the planes for the planned flights, the crews, and maintenance for the planes. Since the planes do fly, tough to convince me that the scheduling is impossible. So, if spending $200 million a month on operations, an optimal schedule could save $20 million, can find a schedule that is approximately optimal and saves all but the last $100,000, then take the $19,900,000 savings and be happy. The claim "we want to show that P = NP so that we can solve all these important problems" has been going on since the cartoon early in Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness'. where the mathematician stood before the business executive and admitted that he could not solve the executive's problem but neither could any of the mathematicians in a long line. Likely nonsense: The mathematician was likely just looking for a long term job and actually not at all interested in solving the executive's problem. Why? Because there was no indication that the executive's problem was large and worst case and needed an exactly optimal solution instead of a nearly optimal solution. The executive's problem might have been relatively easy to solve, with a nearly optimal solution and maybe with an exactly optimal solution. Indeed, the book was from Bell Labs where one of their interests was network design. Well, since the phones did work, somehow Bell did find feasible solutions. Optimal? Maybe not. So, what was "the executive's problem" that was in NP-complete and "too difficult to solve?". Maybe he just wanted to design a telecommunications network to have the needed performance and reliability and, otherwise, get the cost down as much as possible or nearly so. Finding an algorithm that shows that P = NP is very likely a significantly different problem, not his problem, and not necessary for his problem. This erroneous belief that all large instances of problems in NP-complete are too difficult to solve is too common: E.g., once I got a problem in allocation of marketing resources. The instance was 0-1 integer linear programming with 40,000 constraints and 600,000 variables. I thought for a day or so, typed in some software, did some Lagrangian relaxation, and in 905 seconds on a 90 MHz PC got a feasible solution guaranteed to be within 0.025% of optimality. Close enough for gumment work! Then, later, as I was considering network design for the Internet, I got an interview at a network design startup in Texas and mentioned the problem with the 600,000 variables. Well, the whole technical staff was on the other side of the table, had heard the horror stories about NP-complete in college, and concluded to a person that I was claiming to have done the impossible and had to be lying. I left without a job offer, and they soon went out of business. By the way, Mother Nature does protein folding, right? Hmm ....

MrBuddyCasino 11y ago

Lets say I want to solve a problem, but I have no idea if it is solvable in polynomial time. Is there a website or a book where I can look that up?

eru 11y ago
Complexity Zoo.

infogulch 11y ago

What about the problem of a solution to P and NP being ambiguous for practical uses? I read this argument somewhere, but can't find it now: Case 1, it's proved that P = NP, and the complexity of solving an NP problem is N^1000. Case 2, it's proved that P != NP, and the complexity of solving an NP problem is N^log log log log N. In both cases, the result is technically correct (case 1 is polynomial, case 2 is exponential), but from a practical standpoint this proof that P != NP is much more world changing than this proof that P = NP. For example, you'd have to have a problem size that's measured in hundreds of digits before even getting to N^3!

eru 11y ago
In practice we find that algorithms in P usually have small exponents. And thus P is a good shorthand for tractable. If case 2 happens, we'll have to change our shorthand to what we actually care about: tractability. Similar arguments apply to case 1. (We know quite a bit about how a proof of NP ?= P could _not_ look like, because people already proved that certain strategies for a proof don't work. I am not sure if we can already rule out N^log log log log N, but it wouldn't surprise me.)
- dllthomas 11y ago
  "In practice we find that algorithms in P usually have small exponents." We find that algorithms we have identified in P usually have small exponents. This may simply be selection bias, if we are poor at coming up with n^4+ algorithms.
- infogulch 11y ago
  So, "P" and "NP" are just one possible set of precise definitions for "tractable" and "intractable", and so far they have aligned nicely so they can be used interchangeably (and it's unlikely to change much).
  - eru 11y ago
    Actually, NP isn't too intractable in practice. We are routinely solving huge instances of NP hard problems these days. There are problems that we hope are hard in the average case. Like breaking cryptography.

swehner 11y ago

The video is misleading when it spreads the idea that "polynomial time" equals "practical," or "fast". It's nice and simple to talk like that, but I don't think it's particularly useful or helpful. For example, there is a linear time algorithm for deciding whether two planar graphs are isomorphic (Hopcroft,Wong 1974). But the constant of the asymptotic time bound of their algorithm so large that it was not useful or practical (see end of abstract, http://dl.acm.org/citation.cfm?id=803896 http://dl.acm.org/citation.cfm?id=803896) Only in 2004 did Kukluk, Holder, Cook publish a quadratic time algorithm, "suitable for practical implementation." http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf http://www.eecs.wsu.edu/~holder/pubs/KuklukJGAA04.pdf More such examples are listed at "Polynomial-time algorithms with huge exponent/constant," http://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant http://cstheory.stackexchange.com/questions/6660/polynomial-...

peeters 11y ago
I think the video addresses it in a fair and approachable manner. It makes it clear that the value is in scaling algorithms to larger inputs, and even shows so in a graph. When dealing with unbounded scaling, the constants typically do not matter.

mottalrd 11y ago

Amazing, thank you for sharing