P, NP, NP Complete, Intractable in layman terms?
in [Theory]
|
Prev: I Guess it's Obvious I also Like to Write [Mythologies of Reason?]
Next: question about "merging" two context-free languages (CFL)
From: Francesco S. Carta on 11 Aug 2010 21:00 Zahid Faizal <zahidfaizal(a)canada.com>, on 11/08/2010 17:31:01, wrote: > The news of Vinay Deolalikar possibly proving that P not-equals NP > prompted me to again attempt to come up with a layman definition of > these terms (not the formal definitions, which are confusing and > circular). Kindly correct me if I am wrong. > > 1). P: A problem that can be solved efficiently > > 2). NP: A problem that can be verified efficiently > > 3). NP Complete: A class of related problems that can be > efficiently verified but for which no efficient solution has been > found yet (and probably none exists). If an efficient solution can be > found for even one of these problems, they can all be solved > efficiently. > > 4). NP Hard: A really hard problem to solve, may or may not be > efficiently verifiable. > > 5). Intractable: A problem with provably no solution (e.g. > Turing Halting Problem) I don't know if you got them perfectly, but reading your list I was able to give more sense to what I've been able to understand on my own about the subject. Thanks for posting it, it helped me completing the whole rough picture. -- FSC - http://userscripts.org/scripts/show/59948 http://fscode.altervista.org - http://sardinias.com
From: Joshua Cranmer on 11 Aug 2010 21:54 On 08/11/2010 08:31 PM, Zahid Faizal wrote: > The news of Vinay Deolalikar possibly proving that P not-equals NP > prompted me to again attempt to come up with a layman definition of > these terms (not the formal definitions, which are confusing and > circular). Kindly correct me if I am wrong. > > 1). P: A problem that can be solved efficiently > > 2). NP: A problem that can be verified efficiently Here, there are two qualifiers that need to be made: 1. P and NP (in addition to NP-complete) are classes of only decision problems--those for which the algorithm will print either YES or NO. 2. "Efficiently" is a vague word. The key requirement here is that the algorithm must be bounded by polynomial time in the size of the input, but I would struggle to come up with a description that is concise, accurate, and nonmathematical. Perhaps one way of thinking about it is an algorithm is efficient if doubling the size of the input multiplies run time by a constant as opposed to squaring it (or worse). > 3). NP Complete: A class of related problems that can be > efficiently verified but for which no efficient solution has been > found yet (and probably none exists). If an efficient solution can be > found for even one of these problems, they can all be solved > efficiently. NP-complete is the class of all (decision) problems for which any NP problem would be "merely" a special case. In other words, solving it "efficiently" allows you to solve any problem in NP "efficiently." Note that this is a case where the common connotation is a bit wrong: applying all reductions the addition problem to subset sum leads to a problem of size ~O(n^48), which is easily intractable. Another way of looking at many NP-complete problems (or NP-hard in general) is that they are problems where our known algorithms boil down to, in essence, "try a large fraction of all possible solutions", where the space of possible solutions is ~O(n!) or greater. > 4). NP Hard: A really hard problem to solve, may or may not be > efficiently verifiable. NP-hard is a generalization of NP-complete. Unlike the other three mentioned classes, NP-hard includes non-decision problems. Roughly speaking, a problem is NP-hard if you can use it to solve an NP-complete problem. An example: the boolean satisfiability problem asks if there exists an assignment for variables that satisfies a given equation; this problem is NP-complete. A related problem is to, given such an equation, find an assignment (if it exists) that would satisfy the equation. This one is NP-hard: clearly, being able to solve the latter allows you to solve the former. That example is particularly poignant for another reason: though the functional problem (find the assignment) and the decision problem (is there an assignment?) are often treated as the same problem, it does indicate that it is possible to show that P=NP and still have it be useless in practical application. One can consider that the solution could be a nonconstructive algorithm: it can tell you that a solution exists but it gives no insight into what the solution would be. Consider the relation between primality testing and factoring. All fast algorithms that I know of can show that a number is not prime but will not deduce a factor of the number in the process. > 5). Intractable: A problem with provably no solution (e.g. > Turing Halting Problem) On this, you are quite wrong. A problem with no solution is called "undecidable". Intractable problems are those that we cannot solve quickly--not in the asymptotic polynomial/exponential case, but in the raw time case. A problem that has runtime n^5 with a low constant coefficient is easily tractable while one with 1e100 * n^2 is easily intractable, even though the latter is asymptotically preferable. An interesting related note is that all of these cases are decided for the worst case solution, so it's possible that a solution exists which is tractable for many "real" applications but intractable in a few special worst cases. This includes, notably, undecidable problems: it is possible to solve an undecidable problem in many common cases, just not for every single case. -- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
From: tchow on 11 Aug 2010 22:07 Keeping in mind that this is for the layman... In article <9dcc8a5d-c1de-48d0-bf8c-62e86e8f0047(a)x18g2000pro.googlegroups.com>, Zahid Faizal <zahidfaizal(a)canada.com> wrote: > 1). P: A problem that can be solved efficiently Reasonable. > 2). NP: A problem that can be verified efficiently Reasonable, though I might phrase it, "a problem whose solutions may not be easy to find, but whose solutions are easily recognizable as correct once they are found." > 3). NP Complete: A class of related problems that can be >efficiently verified but for which no efficient solution has been >found yet (and probably none exists). If an efficient solution can be >found for even one of these problems, they can all be solved >efficiently. Reasonable, though I would phrase it, "The hardest problems in NP. If an efficient solution can be found for even one of these problems, then all problems in NP can be solved efficiently." > 4). NP Hard: A really hard problem to solve, may or may not be >efficiently verifiable. Not bad, but I would say, "A problem whose efficient solution would lead to the efficient solution of every problem in NP, but which may not itself be in NP. If an NP-hard problem is in NP then it is NP-complete." > 5). Intractable: A problem with provably no solution (e.g. >Turing Halting Problem) This term is not strictly speaking a technical term and is used in different ways by different people. Some people use it the way you say, but others just use it to mean "hard." -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: James Waldby on 11 Aug 2010 23:19 On Wed, 11 Aug 2010 17:31:01 -0700, Zahid Faizal wrote: > The news of Vinay Deolalikar possibly proving that P not-equals NP > prompted me to again attempt to come up with a layman definition of > these terms (not the formal definitions, which are confusing and > circular). Kindly correct me if I am wrong. [snipped notions about P, NP, NP Complete, NP Hard] > 5). Intractable: A problem with provably no solution (e.g. > Turing Halting Problem) As others have mentioned, that isn't normal usage. See eg <http://en.wikipedia.org/wiki/Intractable_problem#Intractability> About Deolalikar's stuff, according to Various Authorities he hasn't got a proof yet; but perhaps will or won't at some future time. Eg see Terence Tao's comments quoted near beginning of current blog page at <http://rjlipton.wordpress.com/> [*]. [*] 11 August entry, with title, ""Deolalikar Responds To Issues About His P≠NP Proof" and direct link <http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/> -- jiw
From: Frederick Williams on 12 Aug 2010 09:30
Zahid Faizal wrote: > > The news of Vinay Deolalikar possibly proving that P not-equals NP > prompted me to again attempt to come up with a layman definition of > these terms (not the formal definitions, which are confusing and > circular). Circular? -- I can't go on, I'll go on. |