From: mva@igloo.df.lth.se (Martin =?iso-8859-1?Q?Wahl=E9n?=) Subject: Re: NP complete? Date: 1 Oct 2001 16:07:09 GMT Newsgroups: sci.math.num-analysis Summary: Difference between NP and NP-complete problems In article <9p9shr$g1u$1@snic.vub.ac.be>, Gunter wrote: >What exactly is meant by this? Does it just mean that the Number of >Parameters is high (meaning a multi-modal search space), or does the NP >stand for something else (also is there a difference between "hard" and >"complete")? NP is a complexity class. NP hard problems are problems outside of NP that all problems in NP (polynomialy) reduce to, NP complete problems are problems in NP that all problems in NP reduce to. NP is the class of problems that can be decided by a nondeterministic turing machine in polynomial time. See Christos H. Papadimitriou , Computational Complexity Martin ============================================================================== From: Christopher Creutzig Subject: Re: NP complete? Date: 02 Oct 2001 13:21:12 +0200 Newsgroups: sci.math.num-analysis "Gunter" writes: [NP complete, NP hard] > What exactly is meant by this? Does it just mean that the Number of > Parameters is high (meaning a multi-modal search space), or does the NP Not really, it is something about "how much more time do we have to invest when the number of parameters increases?", i.e., a complexity argument. For example, multiplying a matrix with a scalar (a complex number) takes constant time for each entry of the matrix, so for an n times n matrix it takes n^2 times some constant time. This is denoted by saying the algorithm is O(n^2), or in words, "quadratic". Multiplying two n times n matrices the obvious way is a cubic algorithm. Both of these are polynomial algorithms, because n^2 and n^3 are polynomial in n. On the other hand, sendig 3^n '*'s to the screen is a problem in O(3^n), since that is the size of the output, and you cannot beat this limit. By the magic of the O, multiplicative constants are dropped, so O(3^n) is the same as O(exp(n)), and I have just described an exponential problem. Exponential problems are nasty, simply because the amount NP is something in between: For each single problem, there is a way to solve it in polynomial time (a polynomial time proof), so NP includes the polynomial time algorithms. For an NP hard problem, however, nothing is known about finding this proof in polynomial time. NP hard problems need not be in NP themselves, but if they are, they are called NP complete. Now, the interesting thing is that once you have an algorithm which solves one NP hard problem in polynomial time, then all the NP complete problems can be solved in polynomial time. This would imply that all NP problems could be solved in polynomial time, something abbreviated as "P=NP". Hardly anyone believes that this was possible. Summary: Do not try to find exact solutions to NP hard problems, you would be running out of time extremely soon when the problems get larger. > stand for something else (also is there a difference between "hard" and > "complete")? NP complete is a special case of NP hard. For all practical purposes, no, there is no difference. It is futile to directly solve any of them unless you can restrict the size of problems. -- +--+ +--+| |+-|+ Christopher Creutzig (ccr@mupad.de) +--+ Tel.: 05251-60-5535 ============================================================================== From: djimenez@cs.utexas.edu (Daniel A. Jimenez) Subject: Re: NP versus NP-complete problems Date: 1 Nov 2001 14:51:17 -0600 Newsgroups: sci.math In article <58b749d6.0110311529.efee16e@posting.google.com>, Geert Batterink wrote: >Hi all, > >Despite some reading in Artificial Intelligence texts I cannot put my >finger on the exact difference between NP-problems and NP-complete >problems. >I hope someone can help my out and tell me the difference in plain >English. >As I understand it, NP-complete problems are more difficult to solve >than NP-problems, but what is it that makes a problem a NP-complete >problem exactly? >Is it just the number of candidate solutions or is there something >else? >Any cleariying comments will be highly appreciated, NP is a set of problems (or, more precisely, a set of languages). An NP-complete problem is a problem in NP that is complete for NP. A language L is NP-complete if L is in NP and, for every other language L' in NP, L' is polynomially reducible to L. That means that an NP-complete problem is at least as hard as anything else in NP. The set of NP-complete problem each have the same hardness (within a polynomial factor), and are the hardest problems in NP. Many problems are in NP without necessarily being NP-complete. If P!=NP, then there are non-trivial problems in NP that are strictly easier than NP. (If P=NP, then all non-trivial problems in NP are also NP-complete. Given the incomplete state of our knowledge of P vs. NP, it can be a little difficult to understand exactly what is harder than what.) See the comp.theory FAQ for more information: http://www.cs.unb.ca/~alopez-o/comp-faq/faq.html -- Daniel A. Jiménez djimenez@cs.utexas.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage ============================================================================== From: kramsay@aol.commangled (Keith Ramsay) Subject: Re: NP versus NP-complete problems Date: 04 Nov 2001 16:16:41 GMT Newsgroups: sci.math In article <9rsck5$5c9$1@zorkmid.cs.utexas.edu>, djimenez@cs.utexas.edu (Daniel A. Jimenez) writes: > If P!=NP, then there are non-trivial problems in NP that are >strictly easier than NP. I think you mean "there are nontrivial problems in NP that are strictly easier than NP-complete". There isn't any "easier than NP"; NP includes all the easiest problems. Keith Ramsay ============================================================================== From: "Ken Payson" Subject: Re: NP versus NP-complete problems Date: Sat, 03 Nov 2001 16:04:16 GMT Newsgroups: sci.math A problem is in the class P if it can be solved in polynomial time on a deterministic turing machine. A problem is in the class NP if it can be solved polynomial time on a non-deterministic turing machine. Also, a proposed solution of an NP problem can be checked for correctness in polynomial time on a deterministic turing machine. In other words P problems are Polynomial time solvable but NP problem are only Polynomial time checkable. (unless P=NP) if x is a problem x in P ---> x in NP (x in NP --> x in P) <--> P=NP There is a subclass of NP called NP complete. One NP complete problem can be transformed to look like another NP complete probelm. If you find a polynomial time solution (on a determinist machine) for a NP complete problem it implies that every other NP complete problem also has a polnomial time solution. If you found a polynomial time solution for an an NP problem that wasn't NP complete it wouldn't have any implications for the rest of the NP problems. There is some confusion caused by language use. If we called a problem NP in ordinary discourse, it would tend to mean that no polynomial time solution was known. But by the definition, all P problems are also NP so for example QuickSort is polynomial time solution to an NP problem. "Geert Batterink" wrote in message news:58b749d6.0110311529.efee16e@posting.google.com... [quote of original message deleted --djr]