8 ms·

What if P = NP?

124 points by caustic 16y ago

lkozma 16y ago
There's a funny poll on P=?NP that William Gasarch conducted among computer scientists: http://www.cs.umd.edu/~gasarch/papers/poll.pdf http://www.cs.umd.edu/~gasarch/papers/poll.pdf Some argue that the question is not as important as it is widely believed to be (see Sariel Har-Peled's opinion in the poll) - many NP hard problems have practical approximations, many P problems are prohibitively costly to solve.
- bdhe 16y ago
  > many NP hard problems have practical approximations, many P problems are prohibitively costly to solve. I don't know if there is more to Sariel Har-Peleed's piece than the one paragraph in the poll, but as of today, most P problems used in practice actually have a very good running time O(n^3) or O(n^4). I don't know if there are too many problems that are in P but only "theoretically". Also, even though P=?NP might not have very practical ramifications, if one believes in the notion of asymptotic complexity, it raises fundamental philosophical questions -- is judging creativity as easy as being creative. As usual Scott Aaronson has excellent material on this question: http://www.scottaaronson.com/blog/?p=459 http://www.scottaaronson.com/blog/?p=459
  - _delirium 16y ago
    I see that piece mentioned a lot, but I don't think it's really in keeping with the existing philosophy or research on computational creativity. There's a lot of disagreement of course, but a vague consensus is that the formalization problem is harder than the computational complexity problem: computers composing novel, good symphonies is not mainly bottlenecked by computational complexity, but because we don't know how to write a program to do it (in any running time). Put differently, why is symphony composition harder than SAT? You can download programs right now to solve huge classes of SAT, but not to compose huge classes of symphonies (David Cope's interesting work notwithstanding). (That example from: http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html)
    - bdhe 16y ago
      That's an interesting read! I think his point is that NP-completeness does not give you an intuition about the hardness of automating creativity. That point is granted. However, if P were equal to NP, then it would imply that we can write algorithms that can automate creativity (Levin's algorithm is an algorithm to solve all NP-complete problems in polynomial time, if P=NP); which will raise an interesting philosophical debate all on its own.
  - lkozma 16y ago
    Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical. I agree about the philosophical questions, but don't they also rely on the practical ramifications of the question? "is judging creativity as easy as being creative" What if P=NP, and for some problem there is a practical polynomial algorithm for checking a solution but only an impractical polynomial algorithm for finding a solution? What I mean is that the philosophical ramifications also depend on the assumption that polynomial~easy.
    - timtadh 16y ago
      >n^3 or n^4 might already be considered impractical in many situation You can always make these arguments for large enough N and short enough time constraints. It is an argument that as an engineer I sympathize with, but as a computer scientist I cannot endorse. The question of P=?NP is a mathematical and philosophical question. The problem of O(N) algorithms being too slow for situation X is an engineering question. So while I recognize and even sympathize with you point, I do not think it detracts from the fundamental importance of the question at stake.
      - lkozma 16y ago
        True, there is the engineering aspect, but I didn't mean that, I was talking about the same fundamental philosophical question you were. That is, "are there problems for which we can easily verify a solution but not easily find one". P=?NP is only relevant to this philosophical question, if we accept that "polynomial" is synonymous with "easy". That is a widely accepted statement, but not entirely obvious. As it was said in the linked poll, even a polynomial running time could hide contants so large, that it is prohibitively large not just today but anytime in the future until the universe collapses upon itself. On the other hand there can be NP-hard problems for which we can find arbitrarily close approximations in reasonable time. The question is how well are our theoretical efforts capturing this intuition.
    - bdhe 16y ago
      > Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical. Ah, so you now you can see how pathetic our understanding of computational complexity is when we consider algorithms that are linear sometimes impractical but we cannot show we can do better than an exponentially worse off bound for SAT instances (Today's best SAT algorithms run in time 2^O(n)).
  - btilly 16y ago
    I don't know if there are too many problems that are in P but only "theoretically". Actually there is a known class of problems that are in P, but only "theoretically"! But for very different reasons than what you are thining of. See http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theor... for a theorem that implies that certain types of graphs are characterized by a finite set of forbidden graphs that cannot be embedded in any form. (I'm being vague about "in any form" here, what I mean is that you can't do things like subdivide an edge and put a point in the middle then say, "Here! I changed it." More formally the forbidden subgraph can't be a minor of the main graph. See http://en.wikipedia.org/wiki/Minor_%28graph_theory%29 http://en.wikipedia.org/wiki/Minor_%28graph_theory%29 for an explanation of what a minor is.) For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.) Any graph that does not contain these anywhere is planar. It turns out a finite forbidden set of minors can always be tested in polynomial time. Therefore an class of graphs that meets the conditions for the Robertson-Seymour theorem has a polynomial time test. Here is the catch. For many classes of graph we can prove that this polynomial time test exists. But we don't actually know what it is. Finding it requires enumerating the finite set of forbidden minors. But we have no way to figure out what they are. For graphs that can be embedded in the plane we know that there are just two. The projective plane turns out to have 138. As of 2004 I know that were nearly 240,000 known for the torus, and this list was not believed to be complete. According to http://www.cs.uvic.ca/~ruskey/Theses/WoodcockMScThesis.pdf http://www.cs.uvic.ca/~ruskey/Theses/WoodcockMScThesis.pdf there were theoretical algorithms that were O(n) and O(n^3), but nobody had ever implemented them and it was suspected that they would be too slow to use in practice. Moving on, consider the set of graphs that can be embedded in 3D without any knots. To the best of my knowledge nobody even has an exponential algorithm for that - yet we know that the problem must be in P. So there you are. A whole family of problems, all of whom are known theoretically to have solutions in P, but for most of them we have no way to find said solutions, and even if we did find them they would likely be too slow to use in practice.
    - derefr 16y ago
      > For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.) Huh. I know this intuitively from doing those "try to connect the three houses to the three respurces without crossing any lines" kind of puzzles when I was younger—but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem. My (puny) knowledge of topology has been made slightly more concrete. :)
- JonnieCache 16y ago
  That poll was very interesting. I particularly enjoyed this "proof:" http://www.cs.cornell.edu/hubes/pnp.htm http://www.cs.cornell.edu/hubes/pnp.htm
  - podperson 16y ago
    Even accepting the leaps, the false underlying assumption is that if P = NP there must be a proof. Goedel's Incompleteness Theorem's key result is that within any logical system there are truths that cannot be proven. It follows that we may never be able to prove that P = NP or P ≠ NP, even though one of the two must be true.
    - Cacti 16y ago
      Actually, there are problems that are neither provably true/false, nor actually true/false. In fact I think a standard counting argument shows that 99.9999...% are in that category.
      - podperson 16y ago
        Yes but incompleteness refers to things that are true but can't be proven to be true. I think you're referring to the idea of prospective axioms which can be proven to be independent of existing axioms (notably the axiom of choice). This is another thing altogether. In the end, knowing enough about something to reduce it to axioms is only the start and not the end of understanding. P = NP wouldn't suddenly trivialize the problems so much as indicate that a polynomial time solution exists somewhere.
arethuza 16y ago
A nice wee Charlie Stross story that begins with news of someone finding a proof of P=NP (Readability recommended): http://www.antipope.org/charlie/blog-static/fiction/toast/toast.html#antibodies http://www.antipope.org/charlie/blog-static/fiction/toast/to...
- burgerbrain 16y ago
  Some people have zombie apocalypse plans. Me? I have P=NP plans.
- deleted 16y ago
  [deleted]
simonsarris 16y ago
There was some good discussion about a P/NP for dummies article a while back, here: http://news.ycombinator.com/item?id=1605415 http://news.ycombinator.com/item?id=1605415 And by the same author as the story above, a good list of reasons for believing that P probably != NP: http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=122
dexen 16y ago
What if the equality (or inequality) of P and NP is unprovable in the general case? Practical considerations aside, it would probably feel like a recursive joke ;-)
- bdhe 16y ago
  I'm sure a lot of people are "worried" about that. Remember, the mathematical community went through the same thing about 80 or so yrs ago when Gödel came up with his Incompleteness Theorem just about when most of the mathematical world believed that were were just a few steps shy of axiomatizing all of mathematics in a consistent manner (see: Hilbert's Second Problem).
- presidentender 16y ago
  The year is 2230. The Nuclear Winter has passed, and the water wars have come. One mathematician - the last of his kind - dares to spend precious time puzzling through theorems, seeking out ancient tomes of knowledge written in arcane symbols. He is searching for a proof which meant something to his ancestors hundreds of years ago. One day, in a dusty library in what used to be called New England, he finds it. Not only through reading the works of others, no, he has proven many new theorems, and his results would have held application to the software efforts of centuries ago. God weeps that there is no software now. But he has at last found it, the final proof: that it cannot be proven that it cannot be proven ... that it cannot be proven conclusively whether P = NP.
  - dexen 16y ago
    The story reads great :D But first and foremost, I like how ``it cannot be proven that...'' is a special kind of negation, much different than the ordinary negation in boolean logic. Is there any formalized logic system with a negation with properties like ``it cannot be proven that...''?
  - space-monkey 16y ago
    I'd go see that movie.
  - shasta 16y ago
lyudmil 16y ago
It would be a boon for laissez-faire capitalism, as it would prove that markets are at least weak-form efficient. Reference: http://arxiv.org/abs/1002.2284 http://arxiv.org/abs/1002.2284
- randallsquared 16y ago
  Support for laissez-faire capitalism doesn't require that markets are efficient in any absolute sense, but only that using force will not produce a more efficient outcome in real-time. But I don't think people argue for markets to be supplanted by force for efficiency reasons, as its already clear that such a solution is intractable unless actor choices are restricted significantly.
  - lyudmil 16y ago
    Correct. I should have said "neo-liberal economics".
  - Tycho 16y ago
    Why did you add the phrase 'in real time' there? I don't follow (sincere question)
    - randallsquared 16y ago
      Because given enough information about preferences and enough time to think about it, coming up with a more efficient solution to a particular distribution problem than the market did seems possible in principle.
      - Tycho 16y ago
        Ah, I'm with you now, thanks.
anorwell 16y ago
Anyone who finds this speculation about "What if P = NP?" interesting should try Impaggliazzo's excellent paper (it's very readable): http://cseweb.ucsd.edu/~russell/average.ps http://cseweb.ucsd.edu/~russell/average.ps
- bdhe 16y ago
  This is a followup, 15 yrs later from the rest of the TCS community: http://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds http://cstheory.stackexchange.com/questions/1026/status-of-i...
tibbon 16y ago
Can someone explain the P=NP thing to me? I've tried looking at the Wikipedia article, but I'm going to admit right not that my computer science/mathematics skills aren't as amazing as I'd like them to be. Wouldn't that mean that N == 1 and that P == P?
- janzer 16y ago
  The NP is just one variable and not N times P, it stands for Nondeterministic Polynomial time. The wikipedia article you want is http://en.wikipedia.org/wiki/P_versus_NP_problem http://en.wikipedia.org/wiki/P_versus_NP_problem
- presidentender 16y ago
  We're not multiplying N by P. P and NP are complexity classes. Essentially, a problem is in class P (for polynomial) if an optimal solution can be found in polynomial time (that is, if the number of steps required to solve the problem is at most a polynomial function of the number of factors to check). So if you have a problem, and you can always solve it in polynomial time, it's in P. A problem is in class NP (for nondeterministic polynomial) if the optimality of any solution can be checked in polynomial time. So if you have what you think is a solution, and you can always verify that in polynomial time, the problem is in NP. We know trivially that NP is a superset of P: any P problem has to be an NP problem, because determining the solution in polynomial time counts as checking that solution in polynomial time. What we're not sure of is whether NP is a proper superset of P: the two could be equivalent, and we could just be overlooking polynomial-time algorithmic solutions to the problems we currently believe to be NP but not P.
  - tibbon 16y ago
    Thanks for the answer. I'm not sure why I was downvoted, because I have looked it up before but just didn't understand. Not everyone gets everything the first time or went to school for CS so I highly appreciate you taking the time to explain. I'm curious also why this problem is so near and dear to many people. I'm not sure I understand the implications.
scythe 16y ago
What would really be interesting is someone finding a nonconstructive proof that P = NP. It would be quite a scramble to find the missing algorithms...
- bdhe 16y ago
  We already have algorithms for all NP problems, by Levin. See: http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-... No one knows whether it runs in polynomial time though! It runs in polytime if P=NP.
  - deleted 16y ago
    [deleted]
  - smallblacksun 16y ago
    "// "Polynomial-time" means it returns "yes" in polynomial time when // the answer should be "yes", and runs forever when it is "no"." That's an odd definition of polynomial time.
    - bdhe 16y ago
      It is just a technicality. If you know an upper bound on the running time you can simply run it for that many time steps and then return "no" if it doesn't halt by then (because it could never thereon answer "yes"). This only works with concrete upper bounds on running time (and not for general decidability).
efnx 16y ago
From the beginning of the article: "We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings." Can someone explain why there are 300 billion trillion pairings instead of 40^2 pairings - 40 repeat pairings - incompatible pairings ?
- wnoise 16y ago
  Pairings involve matching everybody. There are indeed O(n^2) (well n*(n-1)/2) ways of constructing the first match. But then the other n-2 people still need to be paired up. The exact number is n!/((n/2)!(2^(n/2))). There are n! ways to order them. Pair each with his neighbor. The order of the pairs doesn't matter (divide by (n/2)!). The order within each pair doesn't matter (divide by 2^(n/2)). Using Stirling's approximation, the log of this is about n log n - (n/2) log (n/2) - (n/2) log 2 = (n/2) log n. The exponential is then n^(n/2). 40^20 is rather large at 109 nonillion. Because we approximated the log, this significantly off. The right answer is 319 sextillion.
  - efnx 16y ago
    I see, they're talking about the number of configurations of pairs, not the number of unique pairs themselves.
  - 27182818284 16y ago
    Thanks for this! I was confused myself. http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%21%282^%28n%2F2%29%29%29%2C+n%3D40 http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%2... seems to give 319830986772877770815625 It can also be done by thinking 39 * 37 * 35 * ... * 1 which also yields the same number. In that way, it is like selecting 1 person, who then has 39 people remaining, then selecting another, who has 37 left to choose from and so on. I was super confused at first why it wasn't just 40 choose 2.
williamdix 16y ago
It makes me feel good about the $200,000 spent on my education that I got to take classes with two of the people mentioned with important results. One of them, Mulmuley, was the most intimidating professor I ever had, and I felt very lucky to get out of that class with a C.
NY_USA_Hacker 16y ago
Okay, the question of P versus NP is important. Now keep in mind that I admitted this when read the rest below: Contention: In this research question of P versus NP and in the paper, we are looking at: (1) A Lot of Hype. (2) A Search for a Very Long Term Academic Job. (3) Significant Amounts of Nonsense. Details: (1) A Lot of Hype. (1.A) Nowhere in the article are there any very good explanations that a polynomial algorithm that shows that P = NP would be fast in any practical sense. Indeed, the article has: "Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems." So, to make such a polynomial algorithm of practical interest, we have to just "suppose" that it will be fast in practical terms. (1.B) With the "suppose" above, the article has: "Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface." No, it's just "scratching" and not "just scratching the surface." I can absolutely, positively assure all readers that there are plenty of reasonably efficient and powerful means to attack such problems in practice now. In fact, the people flying airplanes, running manufacturing plants, designing large telecommunications networks, etc. are not much interested in attacking these problems with optimization. The main reason is: They just don't want to be bothered. In particular, these problems have long been part of the field of 'operations research', that has long been a dead field, a "late parrot", a dead duck. Just what is it about people don't want to be bothered that is so difficult for the author of the paper to understand? (1.C) Solve It All. The suggestion in the article is that the question of P versus NP is the grand question and, thus, the last big problem in computational complexity. Let's see: For many of the optimization problems in, say, airline scheduling, manufacturing scheduling, telecommunications network design, given an optimal solution, over the coming few hours, days, or weeks, real world uncertainty commonly will make that solution out of date and far from 'optimal'. So, the real problem that needs to be attacked in practice is optimization over time under uncertainty, and there was no hint of such problems in the paper or that showing that P = NP would provide solutions. Net, it is not clear from the paper that the NP-complete problems cover all the challenges that remain. A lot of hype. (2) A Search for a Very Long Term Academic Job. The paper ends with: "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." Of course he hopes not: As long as the problem is not solved, a lot of researchers chipping away on apparently quite distant parts continue to have a very stable career! (3) Significant Amounts of Nonsense. The article has: "everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste." Glad he's interested in "less waste". But, let's see on three points: (3.A) Approximately Optimal Commonly in such cost minimization optimization problems now, we report two numbers: First we report the cost of the feasible, but perhaps not optimal, solution we did find. Second we report a lower bound on the cost of an optimal solution. When these two numbers are close for our practical problem, we quit and accept the feasible and approximately optimal solution. The last time I did this, I had a 0-1 integer linear program with 600,000 variables and 40,013 constraints and found a feasible solution with cost only 0.025% higher than the lower bound, in 905 seconds on a 90 mHz PC. So, the practical problem is, can we find techniques that get a feasible solution and a lower bound close enough for practice nearly always on the practical problems we face? Nowhere did the paper recognize this problem or indicate a close connection with the challenge of P versus NP. Yes, we can ask, given the optimization problem and a cost c, is there a feasible solution with cost less than c? So, since we can check a proposed solution quickly, this is a problem in NP. Then on this problem we can do a binary search on c and converge to optimality. So if this NP problem is in P, then with the binary search our optimal algorithm is also in P. But it is not clear if this is the same problem as, can we get a feasible solution (in reasonable time, nearly always, on our practical problems) with cost c only 1% higher than a lower bound u? Or only 1% above the cost of an optimal solution (we don't know the cost of an optimal solution). So, the question P versus NP is much more difficult than demanded by practice. (3.B) The Big Savings. The paper has, "everything will be much more efficient." This conclusion is unsupported, wildly unjustified, and from experience nonsense. It is not the least bit clear that optimal solutions will on average cost significantly less than the approximately optimal solutions commonly available now. (3.C) The Cartoon. Early in the reference, Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. and praised in the paper, is a cartoon with an executive sitting behind a desk, a researcher standing just in front of the desk and stretching behind him over the horizon a long line of researchers, and the researcher explaining to the executive that he, the researcher, can't solve the executive's problem but neither can any of the researchers in the long line because none of them could settle P versus NP. Nonsense. Made up, junk-think, make-work, prof-scam, busy-work nonsense: The executive's problem was just to save nearly all the money nearly all the time on the real problems, or at least to save some significant money sometimes, and not to guarantee to save all the money, down to the last tiny fraction of one penny, with polynomial computer time, on worst case problems, the worst that can exist even in theory. Instead the researcher deliberately bamboozled the executive by converting his problem into one the researcher could have an excuse to work on for the rest of his career without getting a solution. There is one more curious point. The paper mentioned: "Consider the traveling salesperson problem again with distances between cities given as the crow flies (Euclidean distance). This problem remains NP-complete but Arora4 gives an efficient algorithm that gets very close to the best possible route." where his reference is Arora, S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sept. 1998), 753–782. While I don't know this paper, there is the highly curious, Richard M. Karp, "The Probabilistic Analysis of Some Combinatorial Search Algorithms," pages 1-19, 'Algorithms and Complexity: New Directions and Recent Results', edited by J. F. Traub, Academic Press, New York, 1976. So, here's what to do: Given a traveling salesman problem in the plane (or any finite dimensional space) with just Euclidean distances, pick a city, from that city build a minimum spanning tree connecting all the cities (well-known to be polynomial and fast). Then for the traveling salesman tour, just do a depth-first traversal of that tree except do not 'backtrack' in the tree and revisit cities and, instead, just take the direct link to the next city to be visited in the traversal. Then for cities selected randomly with meager and reasonable assumptions, and as the number of cities n grows, the solutions have distance as close as we please to optimality with probability as high as we please less than 1. So, for big problems, as long as all we are trying to do is save some travel distance, no problem. For small problems, enumerate! Broadly, the question of P versus NP does not connect very well with the real needs of optimization in practice. Ah, never let the real facts get in the way of an exciting story!
timinman 16y ago
Thanks, that's the first of these P = NP posts that explained it for someone uninitiated to the discussion!
timinman 16y ago
Thanks, that's the first of these P = NP posts that explained it for someone uninitiated to the discussion!
Tycho 16y ago
If aliens arrived and told us P is not NP, would it still be worth trying to prove? What do you gain from the negative (except freed time to tackle other problems)?

124 points by caustic 16y ago

There's a funny poll on P=?NP that William Gasarch conducted among computer scientists: http://www.cs.umd.edu/~gasarch/papers/poll.pdf http://www.cs.umd.edu/~gasarch/papers/poll.pdf Some argue that the question is not as important as it is widely believed to be (see Sariel Har-Peled's opinion in the poll) - many NP hard problems have practical approximations, many P problems are prohibitively costly to solve.

bdhe 16y ago
> many NP hard problems have practical approximations, many P problems are prohibitively costly to solve. I don't know if there is more to Sariel Har-Peleed's piece than the one paragraph in the poll, but as of today, most P problems used in practice actually have a very good running time O(n^3) or O(n^4). I don't know if there are too many problems that are in P but only "theoretically". Also, even though P=?NP might not have very practical ramifications, if one believes in the notion of asymptotic complexity, it raises fundamental philosophical questions -- is judging creativity as easy as being creative. As usual Scott Aaronson has excellent material on this question: http://www.scottaaronson.com/blog/?p=459 http://www.scottaaronson.com/blog/?p=459
- _delirium 16y ago
  I see that piece mentioned a lot, but I don't think it's really in keeping with the existing philosophy or research on computational creativity. There's a lot of disagreement of course, but a vague consensus is that the formalization problem is harder than the computational complexity problem: computers composing novel, good symphonies is not mainly bottlenecked by computational complexity, but because we don't know how to write a program to do it (in any running time). Put differently, why is symphony composition harder than SAT? You can download programs right now to solve huge classes of SAT, but not to compose huge classes of symphonies (David Cope's interesting work notwithstanding). (That example from: http://www.kmjn.org/notes/nphard_not_always_hard.html http://www.kmjn.org/notes/nphard_not_always_hard.html)
  - bdhe 16y ago
    That's an interesting read! I think his point is that NP-completeness does not give you an intuition about the hardness of automating creativity. That point is granted. However, if P were equal to NP, then it would imply that we can write algorithms that can automate creativity (Levin's algorithm is an algorithm to solve all NP-complete problems in polynomial time, if P=NP); which will raise an interesting philosophical debate all on its own.
- lkozma 16y ago
  Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical. I agree about the philosophical questions, but don't they also rely on the practical ramifications of the question? "is judging creativity as easy as being creative" What if P=NP, and for some problem there is a practical polynomial algorithm for checking a solution but only an impractical polynomial algorithm for finding a solution? What I mean is that the philosophical ramifications also depend on the assumption that polynomial~easy.
  - timtadh 16y ago
    >n^3 or n^4 might already be considered impractical in many situation You can always make these arguments for large enough N and short enough time constraints. It is an argument that as an engineer I sympathize with, but as a computer scientist I cannot endorse. The question of P=?NP is a mathematical and philosophical question. The problem of O(N) algorithms being too slow for situation X is an engineering question. So while I recognize and even sympathize with you point, I do not think it detracts from the fundamental importance of the question at stake.
    - lkozma 16y ago
      True, there is the engineering aspect, but I didn't mean that, I was talking about the same fundamental philosophical question you were. That is, "are there problems for which we can easily verify a solution but not easily find one". P=?NP is only relevant to this philosophical question, if we accept that "polynomial" is synonymous with "easy". That is a widely accepted statement, but not entirely obvious. As it was said in the linked poll, even a polynomial running time could hide contants so large, that it is prohibitively large not just today but anytime in the future until the universe collapses upon itself. On the other hand there can be NP-hard problems for which we can find arbitrarily close approximations in reasonable time. The question is how well are our theoretical efforts capturing this intuition.
  - bdhe 16y ago
    > Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical. Ah, so you now you can see how pathetic our understanding of computational complexity is when we consider algorithms that are linear sometimes impractical but we cannot show we can do better than an exponentially worse off bound for SAT instances (Today's best SAT algorithms run in time 2^O(n)).
- btilly 16y ago
  I don't know if there are too many problems that are in P but only "theoretically". Actually there is a known class of problems that are in P, but only "theoretically"! But for very different reasons than what you are thining of. See http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theor... for a theorem that implies that certain types of graphs are characterized by a finite set of forbidden graphs that cannot be embedded in any form. (I'm being vague about "in any form" here, what I mean is that you can't do things like subdivide an edge and put a point in the middle then say, "Here! I changed it." More formally the forbidden subgraph can't be a minor of the main graph. See http://en.wikipedia.org/wiki/Minor_%28graph_theory%29 http://en.wikipedia.org/wiki/Minor_%28graph_theory%29 for an explanation of what a minor is.) For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.) Any graph that does not contain these anywhere is planar. It turns out a finite forbidden set of minors can always be tested in polynomial time. Therefore an class of graphs that meets the conditions for the Robertson-Seymour theorem has a polynomial time test. Here is the catch. For many classes of graph we can prove that this polynomial time test exists. But we don't actually know what it is. Finding it requires enumerating the finite set of forbidden minors. But we have no way to figure out what they are. For graphs that can be embedded in the plane we know that there are just two. The projective plane turns out to have 138. As of 2004 I know that were nearly 240,000 known for the torus, and this list was not believed to be complete. According to http://www.cs.uvic.ca/~ruskey/Theses/WoodcockMScThesis.pdf http://www.cs.uvic.ca/~ruskey/Theses/WoodcockMScThesis.pdf there were theoretical algorithms that were O(n) and O(n^3), but nobody had ever implemented them and it was suspected that they would be too slow to use in practice. Moving on, consider the set of graphs that can be embedded in 3D without any knots. To the best of my knowledge nobody even has an exponential algorithm for that - yet we know that the problem must be in P. So there you are. A whole family of problems, all of whom are known theoretically to have solutions in P, but for most of them we have no way to find said solutions, and even if we did find them they would likely be too slow to use in practice.
  - derefr 16y ago
    > For instance planar graphs cannot contain in any form 5 points that all connect to each other, nor two collections of 3 points that all connect to each other. (These are known as K5 and K3,3.) Huh. I know this intuitively from doing those "try to connect the three houses to the three respurces without crossing any lines" kind of puzzles when I was younger—but I never made the connection that this kind of puzzle is basically the proof of the four-color theorem. My (puny) knowledge of topology has been made slightly more concrete. :)
JonnieCache 16y ago
That poll was very interesting. I particularly enjoyed this "proof:" http://www.cs.cornell.edu/hubes/pnp.htm http://www.cs.cornell.edu/hubes/pnp.htm
- podperson 16y ago
  Even accepting the leaps, the false underlying assumption is that if P = NP there must be a proof. Goedel's Incompleteness Theorem's key result is that within any logical system there are truths that cannot be proven. It follows that we may never be able to prove that P = NP or P ≠ NP, even though one of the two must be true.
  - Cacti 16y ago
    Actually, there are problems that are neither provably true/false, nor actually true/false. In fact I think a standard counting argument shows that 99.9999...% are in that category.
    - podperson 16y ago
      Yes but incompleteness refers to things that are true but can't be proven to be true. I think you're referring to the idea of prospective axioms which can be proven to be independent of existing axioms (notably the axiom of choice). This is another thing altogether. In the end, knowing enough about something to reduce it to axioms is only the start and not the end of understanding. P = NP wouldn't suddenly trivialize the problems so much as indicate that a polynomial time solution exists somewhere.

arethuza 16y ago

A nice wee Charlie Stross story that begins with news of someone finding a proof of P=NP (Readability recommended): http://www.antipope.org/charlie/blog-static/fiction/toast/toast.html#antibodies http://www.antipope.org/charlie/blog-static/fiction/toast/to...

burgerbrain 16y ago
Some people have zombie apocalypse plans. Me? I have P=NP plans.
deleted 16y ago
[deleted]

simonsarris 16y ago

There was some good discussion about a P/NP for dummies article a while back, here: http://news.ycombinator.com/item?id=1605415 http://news.ycombinator.com/item?id=1605415 And by the same author as the story above, a good list of reasons for believing that P probably != NP: http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=122

dexen 16y ago

What if the equality (or inequality) of P and NP is unprovable in the general case? Practical considerations aside, it would probably feel like a recursive joke ;-)

bdhe 16y ago
I'm sure a lot of people are "worried" about that. Remember, the mathematical community went through the same thing about 80 or so yrs ago when Gödel came up with his Incompleteness Theorem just about when most of the mathematical world believed that were were just a few steps shy of axiomatizing all of mathematics in a consistent manner (see: Hilbert's Second Problem).
presidentender 16y ago
The year is 2230. The Nuclear Winter has passed, and the water wars have come. One mathematician - the last of his kind - dares to spend precious time puzzling through theorems, seeking out ancient tomes of knowledge written in arcane symbols. He is searching for a proof which meant something to his ancestors hundreds of years ago. One day, in a dusty library in what used to be called New England, he finds it. Not only through reading the works of others, no, he has proven many new theorems, and his results would have held application to the software efforts of centuries ago. God weeps that there is no software now. But he has at last found it, the final proof: that it cannot be proven that it cannot be proven ... that it cannot be proven conclusively whether P = NP.
- dexen 16y ago
  The story reads great :D But first and foremost, I like how ``it cannot be proven that...'' is a special kind of negation, much different than the ordinary negation in boolean logic. Is there any formalized logic system with a negation with properties like ``it cannot be proven that...''?
- space-monkey 16y ago
  I'd go see that movie.
- shasta 16y ago

lyudmil 16y ago

It would be a boon for laissez-faire capitalism, as it would prove that markets are at least weak-form efficient. Reference: http://arxiv.org/abs/1002.2284 http://arxiv.org/abs/1002.2284

randallsquared 16y ago
Support for laissez-faire capitalism doesn't require that markets are efficient in any absolute sense, but only that using force will not produce a more efficient outcome in real-time. But I don't think people argue for markets to be supplanted by force for efficiency reasons, as its already clear that such a solution is intractable unless actor choices are restricted significantly.
- lyudmil 16y ago
  Correct. I should have said "neo-liberal economics".
- Tycho 16y ago
  Why did you add the phrase 'in real time' there? I don't follow (sincere question)
  - randallsquared 16y ago
    Because given enough information about preferences and enough time to think about it, coming up with a more efficient solution to a particular distribution problem than the market did seems possible in principle.
    - Tycho 16y ago
      Ah, I'm with you now, thanks.

anorwell 16y ago

Anyone who finds this speculation about "What if P = NP?" interesting should try Impaggliazzo's excellent paper (it's very readable): http://cseweb.ucsd.edu/~russell/average.ps http://cseweb.ucsd.edu/~russell/average.ps

bdhe 16y ago
This is a followup, 15 yrs later from the rest of the TCS community: http://cstheory.stackexchange.com/questions/1026/status-of-impagliazzos-worlds http://cstheory.stackexchange.com/questions/1026/status-of-i...

tibbon 16y ago

Can someone explain the P=NP thing to me? I've tried looking at the Wikipedia article, but I'm going to admit right not that my computer science/mathematics skills aren't as amazing as I'd like them to be. Wouldn't that mean that N == 1 and that P == P?

janzer 16y ago
The NP is just one variable and not N times P, it stands for Nondeterministic Polynomial time. The wikipedia article you want is http://en.wikipedia.org/wiki/P_versus_NP_problem http://en.wikipedia.org/wiki/P_versus_NP_problem
presidentender 16y ago
We're not multiplying N by P. P and NP are complexity classes. Essentially, a problem is in class P (for polynomial) if an optimal solution can be found in polynomial time (that is, if the number of steps required to solve the problem is at most a polynomial function of the number of factors to check). So if you have a problem, and you can always solve it in polynomial time, it's in P. A problem is in class NP (for nondeterministic polynomial) if the optimality of any solution can be checked in polynomial time. So if you have what you think is a solution, and you can always verify that in polynomial time, the problem is in NP. We know trivially that NP is a superset of P: any P problem has to be an NP problem, because determining the solution in polynomial time counts as checking that solution in polynomial time. What we're not sure of is whether NP is a proper superset of P: the two could be equivalent, and we could just be overlooking polynomial-time algorithmic solutions to the problems we currently believe to be NP but not P.
- tibbon 16y ago
  Thanks for the answer. I'm not sure why I was downvoted, because I have looked it up before but just didn't understand. Not everyone gets everything the first time or went to school for CS so I highly appreciate you taking the time to explain. I'm curious also why this problem is so near and dear to many people. I'm not sure I understand the implications.

scythe 16y ago

What would really be interesting is someone finding a nonconstructive proof that P = NP. It would be quite a scramble to find the missing algorithms...

bdhe 16y ago
We already have algorithms for all NP problems, by Levin. See: http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-... No one knows whether it runs in polynomial time though! It runs in polytime if P=NP.
- deleted 16y ago
  [deleted]
- smallblacksun 16y ago
  "// "Polynomial-time" means it returns "yes" in polynomial time when // the answer should be "yes", and runs forever when it is "no"." That's an odd definition of polynomial time.
  - bdhe 16y ago
    It is just a technicality. If you know an upper bound on the running time you can simply run it for that many time steps and then return "no" if it doesn't halt by then (because it could never thereon answer "yes"). This only works with concrete upper bounds on running time (and not for general decidability).

efnx 16y ago

From the beginning of the article: "We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings." Can someone explain why there are 300 billion trillion pairings instead of 40^2 pairings - 40 repeat pairings - incompatible pairings ?

wnoise 16y ago
Pairings involve matching everybody. There are indeed O(n^2) (well n*(n-1)/2) ways of constructing the first match. But then the other n-2 people still need to be paired up. The exact number is n!/((n/2)!(2^(n/2))). There are n! ways to order them. Pair each with his neighbor. The order of the pairs doesn't matter (divide by (n/2)!). The order within each pair doesn't matter (divide by 2^(n/2)). Using Stirling's approximation, the log of this is about n log n - (n/2) log (n/2) - (n/2) log 2 = (n/2) log n. The exponential is then n^(n/2). 40^20 is rather large at 109 nonillion. Because we approximated the log, this significantly off. The right answer is 319 sextillion.
- efnx 16y ago
  I see, they're talking about the number of configurations of pairs, not the number of unique pairs themselves.
- 27182818284 16y ago
  Thanks for this! I was confused myself. http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%21%282^%28n%2F2%29%29%29%2C+n%3D40 http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%2... seems to give 319830986772877770815625 It can also be done by thinking 39 * 37 * 35 * ... * 1 which also yields the same number. In that way, it is like selecting 1 person, who then has 39 people remaining, then selecting another, who has 37 left to choose from and so on. I was super confused at first why it wasn't just 40 choose 2.

williamdix 16y ago

It makes me feel good about the $200,000 spent on my education that I got to take classes with two of the people mentioned with important results. One of them, Mulmuley, was the most intimidating professor I ever had, and I felt very lucky to get out of that class with a C.

NY_USA_Hacker 16y ago

Okay, the question of P versus NP is important. Now keep in mind that I admitted this when read the rest below: Contention: In this research question of P versus NP and in the paper, we are looking at: (1) A Lot of Hype. (2) A Search for a Very Long Term Academic Job. (3) Significant Amounts of Nonsense. Details: (1) A Lot of Hype. (1.A) Nowhere in the article are there any very good explanations that a polynomial algorithm that shows that P = NP would be fast in any practical sense. Indeed, the article has: "Technically we could have P = NP, but not have practical algorithms for most NP-complete problems. But suppose in fact we do have very quick algorithms for all these problems." So, to make such a polynomial algorithm of practical interest, we have to just "suppose" that it will be fast in practical terms. (1.B) With the "suppose" above, the article has: "Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface." No, it's just "scratching" and not "just scratching the surface." I can absolutely, positively assure all readers that there are plenty of reasonably efficient and powerful means to attack such problems in practice now. In fact, the people flying airplanes, running manufacturing plants, designing large telecommunications networks, etc. are not much interested in attacking these problems with optimization. The main reason is: They just don't want to be bothered. In particular, these problems have long been part of the field of 'operations research', that has long been a dead field, a "late parrot", a dead duck. Just what is it about people don't want to be bothered that is so difficult for the author of the paper to understand? (1.C) Solve It All. The suggestion in the article is that the question of P versus NP is the grand question and, thus, the last big problem in computational complexity. Let's see: For many of the optimization problems in, say, airline scheduling, manufacturing scheduling, telecommunications network design, given an optimal solution, over the coming few hours, days, or weeks, real world uncertainty commonly will make that solution out of date and far from 'optimal'. So, the real problem that needs to be attacked in practice is optimization over time under uncertainty, and there was no hint of such problems in the paper or that showing that P = NP would provide solutions. Net, it is not clear from the paper that the NP-complete problems cover all the challenges that remain. A lot of hype. (2) A Search for a Very Long Term Academic Job. The paper ends with: "Perhaps we will see a resolution of the P versus NP problem in the near future but I almost hope not." Of course he hopes not: As long as the problem is not solved, a lot of researchers chipping away on apparently quite distant parts continue to have a very stable career! (3) Significant Amounts of Nonsense. The article has: "everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste." Glad he's interested in "less waste". But, let's see on three points: (3.A) Approximately Optimal Commonly in such cost minimization optimization problems now, we report two numbers: First we report the cost of the feasible, but perhaps not optimal, solution we did find. Second we report a lower bound on the cost of an optimal solution. When these two numbers are close for our practical problem, we quit and accept the feasible and approximately optimal solution. The last time I did this, I had a 0-1 integer linear program with 600,000 variables and 40,013 constraints and found a feasible solution with cost only 0.025% higher than the lower bound, in 905 seconds on a 90 mHz PC. So, the practical problem is, can we find techniques that get a feasible solution and a lower bound close enough for practice nearly always on the practical problems we face? Nowhere did the paper recognize this problem or indicate a close connection with the challenge of P versus NP. Yes, we can ask, given the optimization problem and a cost c, is there a feasible solution with cost less than c? So, since we can check a proposed solution quickly, this is a problem in NP. Then on this problem we can do a binary search on c and converge to optimality. So if this NP problem is in P, then with the binary search our optimal algorithm is also in P. But it is not clear if this is the same problem as, can we get a feasible solution (in reasonable time, nearly always, on our practical problems) with cost c only 1% higher than a lower bound u? Or only 1% above the cost of an optimal solution (we don't know the cost of an optimal solution). So, the question P versus NP is much more difficult than demanded by practice. (3.B) The Big Savings. The paper has, "everything will be much more efficient." This conclusion is unsupported, wildly unjustified, and from experience nonsense. It is not the least bit clear that optimal solutions will on average cost significantly less than the approximately optimal solutions commonly available now. (3.C) The Cartoon. Early in the reference, Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979. and praised in the paper, is a cartoon with an executive sitting behind a desk, a researcher standing just in front of the desk and stretching behind him over the horizon a long line of researchers, and the researcher explaining to the executive that he, the researcher, can't solve the executive's problem but neither can any of the researchers in the long line because none of them could settle P versus NP. Nonsense. Made up, junk-think, make-work, prof-scam, busy-work nonsense: The executive's problem was just to save nearly all the money nearly all the time on the real problems, or at least to save some significant money sometimes, and not to guarantee to save all the money, down to the last tiny fraction of one penny, with polynomial computer time, on worst case problems, the worst that can exist even in theory. Instead the researcher deliberately bamboozled the executive by converting his problem into one the researcher could have an excuse to work on for the rest of his career without getting a solution. There is one more curious point. The paper mentioned: "Consider the traveling salesperson problem again with distances between cities given as the crow flies (Euclidean distance). This problem remains NP-complete but Arora4 gives an efficient algorithm that gets very close to the best possible route." where his reference is Arora, S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sept. 1998), 753–782. While I don't know this paper, there is the highly curious, Richard M. Karp, "The Probabilistic Analysis of Some Combinatorial Search Algorithms," pages 1-19, 'Algorithms and Complexity: New Directions and Recent Results', edited by J. F. Traub, Academic Press, New York, 1976. So, here's what to do: Given a traveling salesman problem in the plane (or any finite dimensional space) with just Euclidean distances, pick a city, from that city build a minimum spanning tree connecting all the cities (well-known to be polynomial and fast). Then for the traveling salesman tour, just do a depth-first traversal of that tree except do not 'backtrack' in the tree and revisit cities and, instead, just take the direct link to the next city to be visited in the traversal. Then for cities selected randomly with meager and reasonable assumptions, and as the number of cities n grows, the solutions have distance as close as we please to optimality with probability as high as we please less than 1. So, for big problems, as long as all we are trying to do is save some travel distance, no problem. For small problems, enumerate! Broadly, the question of P versus NP does not connect very well with the real needs of optimization in practice. Ah, never let the real facts get in the way of an exciting story!

timinman 16y ago

Thanks, that's the first of these P = NP posts that explained it for someone uninitiated to the discussion!

timinman 16y ago

Thanks, that's the first of these P = NP posts that explained it for someone uninitiated to the discussion!

Tycho 16y ago

If aliens arrived and told us P is not NP, would it still be worth trying to prove? What do you gain from the negative (except freed time to tackle other problems)?