Talk:NP-complete

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Discrete mathematics
One of the 500 most frequently viewed mathematics articles.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents

[edit] Subset sum problem

"no one knows a significantly faster way to solve the problem than to try every single possible subset, which is very slow." I cut this. There is actually a faster way to solve it that can be found on the linked page. It's not efficient, but it is much better than trying all combinations. —Preceding unsigned comment added by 86.144.186.205 (talk) 17:26, August 26, 2007 (UTC)

The question is whether this is really significantly faster. Cutting this also makes it sound like we know for sure there is no efficient algorithm. --Mellum 21:44, 26 August 2007 (UTC)

Yes it's miles faster. Trying every possible subset takes O(2nN) time. It is possible to solve the problem in O(2n/2N) time with the fastest method. The method is described under the heading 'Exponential time algorithm' on the Subset sum problem page. Putting that statement back when it is disproven on another page is silly —Preceding unsigned comment added by 86.156.53.169 (talk) 20:50, August 27, 2007 (UTC)

I suppose this is simply a difference in the interpretation of the term "significantly". Let it suffice to say that no polynomial-time algorithm is known. Dcoetzee 00:02, 28 August 2007 (UTC)

I worked on the assumption that someone might actually try to implement a method in code. In practise the speed difference would be huge and a programmer would want to know about it.

I'd like to suggest that the first example be based on the Traveling Salesman problem. It's much easier for the common person who's not involved in complexity theory to understand as a practical example in my opinion. Also, where do we have pointers to Statistical Physics, Thermodynamics and Self Organizing systems? This seems a significant omission.—Preceding unsigned comment added by 86.156.53.247 (talk) 21:59, August 28, 2007 (UTC) 75.211.0.29 (talk) 18:58, 16 May 2008 (UTC)

[edit] Accuracy

I don't like the word "likely" in this context. Either something is in P or it isn't. We just don't know which one it is yet. What we do know is that if any NP-hard problem is in P then all NP problems are in P.

Lawrence D'Anna


There seem to be some contradictions in this page. First it says "the NP-complete problems are the hardest problems in NP" and later it says "It isn't really correct to say that NP-complete problems are the hardest problems in NP". I didn't update the page because I am not an expert in this, but would someone please consider fixing this confusing bit?

Thanks,

Rodrigo de Salvo Braz


"It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal, there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these problems may actually have higher complexity than some of the NP-complete problems."

I've heard of phase transitions in NP-complete problems. How does one know that, if P is not equal to NP, then there are problems that are in NP but neither in P nor in NP-complete?

Thanks

David Bernier


There is a detailed explanation on pages 154-155 of Garey and Johnson. It follows from a 1975 theorem of Ladner that if P is not equal to NP, then for every NP-complete problem, there is a subproblem that can be recognized in polynomial time that is neither NP-complete nor in P. Dominus 21:22 Mar 14, 2003 (UTC)

NP-complete are the hardest problems in NP by definition (A problem is NP-complete if it belongs to NP and it can be used to solve any NP problem through a polynomial time reduction). SAT was proven to be NP complete by Cook. Other problems were proven to be NP-complete by solving the SAT problem with them. Jan David Mol 12:10 Jun 2, 2003 (UTC)

Might it be a good idea to change 'problems' in the first line (or even throughout) to 'decision problems'? See the wikipedia page on NP-equivalent for my reason. Léon Planken 22:29 Jun 19, 2003 (UTC)

Hi, does this following thing imply subexponential time for NP-complete problem? i can't find the manuscript but i saw it cited somewhere. does anyone know/read the mansucript? W.D. Smith. Finding the optimum N-city traveling salesman tour in the Euclidean plane in subexponential time and polynomial space. Manuscript, 1988. 68.121.211.14 01:51, 21 Apr 2005 (UTC)

The planar TSP problem is not NP-complete, as far as I know. I don't believe there is any subexponential algorithm for an NP-complete problem (unless something like O(2^n/log n) counts). Deco 06:13, 21 Apr 2005 (UTC)

planar tsp is definitely NP complete from reduction from planar ham cycle 68.121.211.14 19:15, 21 Apr 2005 (UTC)

Oops, okay. You're right, it's safer this way anyway (who knows what people will find). Deco 05:42, 22 Apr 2005 (UTC)
Correct me if I'm wrong, but planar Hamiltonian cycle is the problem of finding a Hamiltonian cycle in a planar graph, i.e. a graph which has no crossing edges when drawn on the plane. Planar TSP is the problem of finding a minimum-cost TSP cycle for points on the plane, i.e. the associated graph is complete with edges between every pair of points, and the distances are the Euclidean distances between the points. I don't see any simple reduction from planar Hamiltonian cycle to planar TSP. 27 Apr 2005


Citing the article:

"In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use that algorithm to solve all NP problems quickly."

I understand that the issue here is not how "quickly" an algorithm can solve a given problem, but instead that you can calculate the time that the algorithm would need to solve the problem.

Carlos Badiola

[edit] NPI

I cut this paragraph:

"It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal, there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these problems may actually have higher complexity than some of the NP-complete problems."

Although P ≠ NP implies that NPI = NP−NPC−P is nonempty, problems in NPI can be reduced to problems in NPC whereas problems in NPC cannot be reduced to problems in NPI. It seems reasonable to describe this state of affairs as "problems in NPC are harder than problems in NPI". So the paragraph is misleading.

Discussion of NPI probably belongs somewhere. Gdr 21:40, 2004 Jul 21 (UTC)

[edit] Imperfect solutions - Approximation

Approximation: An algorithm that quickly finds a suboptimal solution that is within a
certain (often known) range of  the optimal one. Not all NP-complete problems have
good approximation algorithms, and for some problems finding a good 
approximation algorithm is enough to solve the problem itself.

In the paragraph above, I don't understand the bolded phrase. Can someone explain? -- Sundar 07:26, Nov 25, 2004 (UTC)

I don't understand it either. I guess what is meant that approximating some problems good is NP-hard and so essentially not easier than solving them exactly. I'll just remove it, since the other approaches don't have their "caveats" listed either.

[edit] Suboptimality

Having got used to the notion of optimality with relation only to performance, it didn't occur to me that it can be used with correctness (in the Approximation algorithms paragraph). May be, this is because I'm not a native speaker of English. Can someone reword it making it clear that we are talking about correctness? -- Sundar 08:33, Feb 3, 2005 (UTC)

[edit] NP-hard

Under "formal definition ...", last paragraph about "NP-hard", it says "For example, choosing the perfect move in certain board games on an arbitrarily large board is (informally) "strictly harder than" any NP problem."

Shouldn't that be "at least as hard as any NP problem" rather than "strictly harder than"? For example, Garey and Johnson, page 109 (first page of chapter 5), says "at least as hard as the NP-complete problems." --Bubba73 00:23, 25 May 2005 (UTC)

With most games, you're right that "at least as hard" is the most we can say at this point. Some forms of Go are EXP-complete, so that it can't be solved in P, but might still be solvable in NP (although probably not). I suppose there might exist games which are strictly outside NP, but I'm not familiar with any. Deco 23:54, 24 May 2005 (UTC)
That paragraph probably needs to be clarified a little more. NP-hard means "at least as hard as", but some problems are "strictly harder". --Bubba73 00:23, 25 May 2005 (UTC)

[edit] Is this problem NP-complete?

I found this problem and wondered if it was NP-complete: You have a bunch of tasks that take different amounts of time and some tasks can't be started until other tasks are finished. You have unlimited resourses, can do different tasks in parallel, and are trying to find the shortest time to complete all the tasks.

I'm going to assume good faith that you're not trying to get us to do your homework for you. What you describe is essentially a scheduling problem, also called job or task sequencing, and was one of Karp's 21 NP-complete problems. He showed it NP-complete by reduction from the knapsack problem. The graph you describe is called a task dependency graph. Technically, the precise problem you describe is actually NP-hard (it's not NP-complete because it's not even a decision problem). Deco 05:24, 19 Jun 2005 (UTC)

Thanks!--SurrealWarrior 18:43, 20 Jun 2005 (UTC)

[edit] Proofs

Why don't we have any np-completness proofs on wikipedia? In a lot of the invidual problem pages I notice that it might mention the kind of reduction involved, but it never goes into detail... Is there a reason for this? -Averisk 08:48, 12 December 2005 (UTC)

Actually we do. Usually we describe proofs in articles associated with particular theorems, such as Cook's theorem. Most NP reductions are simple enough though that there's no reason we couldn't include them in the articles for the problems (or at least a proof sketch). One issue, however, is that books usually present reductions in a specific order to avoid relying on circular reasoning, for example reducing two problems to each other — this is more difficult in our flat, interlinked article organization. Deco 09:02, 12 December 2005 (UTC)
Wow, fast response. Yes I see what you mean. Maybe we could make seperate pages for the proofs and follow a specific order like you said? -Averisk 09:14, 12 December 2005 (UTC)

[edit] Travelling salesman problem is not NP-complete

This article is rather careless: it repeatedly claims that the travelling salesman problem is NP-complete. This isn't the case: the TSP is a function problem and only decision problems can be NP-complete. (TSP is complete for FPNP.) Of course, there is a decision version of the TSP that is NP-complete (given a weighted graph and a bound k, is there a tour with total weight < k?). But that's not what people usually mean when they say "TSP": they want to know the actual tour!

There are similar problems with some of the other problems mentioned (e.g. in Hamilton path we generally want the path, in Boolean satisfiability we want the satisfying assignment and so on. I've made one change to help with this, but it needs more work. Many authors adopt a convention of using all-caps for decision problems (thus "Hamilton path" vs. HAMILTON PATH). Gdr 21:59, 6 January 2006 (UTC)

I agree that we should be precise, but it is fairly common especially in informal forums to talk about the function problem when one really means the decision problem. One could argue that "traveling salesman problem" is an ambiguous term that can refer to either version. If we are to be precise about this though, let's adopt a convention that avoids irritating verbosity, such as the all-caps thing you describe. Deco 22:09, 6 January 2006 (UTC)

[edit] Arbitrary reward

I have removed the following statement:

Nobody has yet been able to prove whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute in Cambridge, MA is offering a $1 million reward to anyone who has a formal proof that P=NP or that P≠NP.

Clearly this is vandalism by some jokester who thinks it would be funny for someone to jump out of their tub in the nude yelling Eureka! when they find a trivial solution to P≠NP. 59.112.43.12 10:15, 4 October 2006 (UTC)

No, it's true, even if P=NP is frustratingly impossible to disprove. Now restored. (Woops, SAT is based on the size of input, not the number of literals.) Davilla 17:09, 4 October 2006 (UTC)

Yes, and CMI is offering a $1 million reward. It's a Millenium Prize Problem. Deco 21:46, 4 October 2006 (UTC)

[edit] So space doesn't matter???

My edits were reverted. Sorry you can't dispute the Space-time_tradeoff. In the P=NP question space is not irrelevant. If space was not a consideration then I should be wining the Nobel prize in mathematics, since I have already done a proof in my homework assignment that ***ALL*** NP class problems can be solved in polynomial time, hence P=NP (if you COMPLETELY ignore space considerations).

Here is an example proof: Start by using DNA computing/(exponentially reproducing cell cultures) to generate 2^N number of input strings in time N. Then use a list ranking algorithm that implements pointer jumping so that it can assign a unique value to all 2^N inputs in time N. Then using a genetically engineered cell culture, create 2^N number of DNA computers in time N to verify all 2^N inputs in at most time and space theta(n^k) (aka poly time and space) in parallel, the only input string remaining is the satisfying answer. Since all NP class algorithms have to be run in polynomial time and space, using the above method can solve all NP problems in polynomial time, but ONLY with an exponential space trade-off. This is a very simple application of massive parallelism. Since I have just proved myself I will not wait to correct the article. If you want to (or do) revert it post your reasons here. I should point out that I am in no way an expert on this topic, but I should also point out that my above logic has been approved by my professor who makes his living off of this topic. --ANONYMOUS COWARD0xC0DE 07:35, 1 December 2006 (UTC)

I'm not familiar with the subject matter, but please see core content policies including verifiability and no original research. If this idea has been published elsewhere, please cite a reliable publication to back up the edits. I imagine that's what other editors more familiar with the matter might say. Thanks for your time. Luna Santin 07:37, 1 December 2006 (UTC)
 At first sight, both examples give the impression that we have now an
 efficient solution of big instances of NP-complete problems as only polynomial
 time is needed. But, it is very important to regard that the exponential
 complexity has not been eliminated, but it has only be shifted from time to
 space. [1]

 Other applications include attacking the governmental encryption scheme DES
 using molecular computers, solving the satisfiability problem, and using DNA
 to factor integers. [2]
However they both reference the same work by Dr. Leonard Adleman who was able to solve a Hamiltonian path problem instance with DNA computations. --ANONYMOUS COWARD0xC0DE 05:41, 23 December 2006 (UTC)
NP is defined using a particular machine model, namely nondeterministic Turing machines. On nondeterministic Turing machines, polynomial time implies polynomial space. Your "proof" does not use nondeterministic Turing machines, and therefore does not apply to NP. --Mellum 08:03, 1 December 2006 (UTC)
I'm talking about
 A consequence of this definition is that if we had a polynomial time algorithm
 for C, we could solve all problems in NP in polynomial time.
and I am also saying that all problems in NP can be solved in polynomial time (it may take all the space of the know universe, but it can still be solved in polynomial time). I can (theoretically) construct a machine to solve all NP class problems in polynomial time, that applies to NP and makes redundant the above quoted statement. Yes non-deterministic turning machines are an integral part of the discussion of NP, but that doesn't mean that massively parallel deterministic algorithms should be ignored in the discussion of np-completeness. --ANONYMOUS COWARD0xC0DE 05:41, 23 December 2006 (UTC)
What does "applies to NP" mean? If it means that any program for your machine can be converted to a program for a nondeterministic Turing machine with only a polynomial slowdown, you would have solved the P vs. NP problem (which seems somewhat unlikely); otherwise, your statement is irrelevant. --Mellum 20:21, 28 December 2006 (UTC)
You said my "proof" does not apply to NP. I vehemently disagree; I have a machine that can solve all NP class problems in polynomial time (see my cited references or my proof for an example), therefore that machine can be considered in the discussion of NP class problems. I am NOT talking about a nondeterministic Turing machine, I am talking about a Massively_parallel deterministic Turing machine (but I'm not talking about a simple supercomputer with thousands of CPU's I'm talking about a DNA computer with billions of "CPU's" or whatever you want to call it). I am not making any statements about P=NP or that P is a strict subset of NP. I am only saying that all NP class problems can be computed in polynomial time at the expense of extra space complexity. This is almost word for word what I have already sourced "But, it is very important to regard that the exponential complexity has not been eliminated, but it has only be shifted from time to space.". So then after you shift it from time to space you now have to ask the P vs. NP question with regard to space. So in the end the P vs. NP question is with regard to parallel "work"=(time×space or time×(number of CPU's)). The article's statement "A consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time." is extremely redundant since all NP class problems can be decided in polynomial time. The people at Complexity_classes_P_and_NP have accepted my edit "In essence, the P = NP question asks: if positive solutions to a YES/NO problem can be verified quickly in polynomial time, can the answers also be computed quickly in polynomial time and space?", because without considering space complexity the entire discussion becomes redundant because all NP class problems can be solved in polynomial time. --ANONYMOUS COWARD0xC0DE 04:55, 30 December 2006 (UTC)
The term "polynomial time" must refer to a particular machine model, since otherwise it is meaningless. In this context, it refers to deterministic Turing machines. If you allow other machines, you might as well take an NP oracle machine and claim that everything in NP can be solved in constant time. But this is merely a shifting of goal posts, and irrelevant to the question at hand. So please don't add your edits again. --Mellum 11:57, 30 December 2006 (UTC)
I agree. You assume that the sentence implies the context of deterministic Turing machines, however that key phrase is not explicitly stated anywhere in that sentence. I never thought to complain on these grounds. The "algorithm" mentioned in the sentence could just as easily be intended for a nondeterministic Turing machine and no such restriction is placed in the sentence. So now the only thing I have left to dispute is whether or not parallel computations are deterministic or not. Just respond to that in my other post(thread) below if you wish. --ANONYMOUS COWARD0xC0DE 12:18, 2 January 2007 (UTC)

All NP and P class problems are subsets of PSPACE therefore I am justified. --ANONYMOUS COWARD0xC0DE 05:22, 30 December 2006 (UTC)

Your argument is not only original research, but is not applicable to the problem. Assuming for argument's sake that you could indeed make each cell in an exponentially reproducing culture do useful verification computation, and you could support the resources needed to grow that culture to useful problem sizes, then you could solve the problem in polynomial time, but this is irrelevant, because the question of whether P = NP is not about whether arbitrary computational mechanisms can solve NP problems in polynomial time, but whether deterministic Turing machines (used in the definition of P) can do so. In fact, your DNA computing/cell culture ideas are supposed physical realisations of a nondeterministic machine, which are often said to be "making copies of themselves" as a way of understanding them. Thus it should be no surprise that they can solve NP problems in polynomial time, since NP is defined as the problems solvable by a nondeterministic machine in polynomial time.
As for the matter of space, deterministic Turing machines as used in the definition of P do not ever consume more space than time, and I'm heading over to Complexity classes P and NP to revert your redundant additions there as well. Deco 00:55, 1 January 2007 (UTC)
User:Mellum beat me to it, thanks. Deco 00:57, 1 January 2007 (UTC)
I am not certain as to what you are calling original research, my assertion that since NP is a subset of PSPACE that I am justified, or my "proof". As far as I know Massively_parallel machines are not nondeterministic, nor are supercomputers. Space concerns are the only thing I am talking about. Let me make this clear I am talking about the sentence "A consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time." I read this sentence as "A consequence of this definition is that since we have a polynomial time algorithm for C, we can solve all problems in NP in polynomial time." Indeed Mellum pointed out that poly-time could just as well be referring to algorithms for nondeterministic Turing machines. Are you saying that supercomputers are not deterministic Turing machines (I agree that non-parallel machines never use more space than time)? I think I may understand why you keep referring to my "proof" as nondeterministic, because when I cited a source, it made use of DNA-computation with nondeterministic aspects, but in my "proof" all possible search paths were formed, which would negate any nondeterministic effects. At the time I wasn't really paying any attention to nondeterminism, just space-time trade-off examples that closely resembled my "proof". I hope that re-clarification helps. Just an observation Mellum stated "Your "proof" does not use nondeterministic Turing machines" yet Deco stated "your DNA computing/cell culture ideas are supposed physical realisations of a nondeterministic machine" so as I briefly assumed in my previous sentence I am assuming one of you are referring to my citation and the other my "proof". --ANONYMOUS COWARD0xC0DE 12:18, 2 January 2007 (UTC)
In short: highly parallelized machines with a fixed number of parallel processors can be simulated by deterministic Turing machines with at most a polynomial factor slowdown, whereas machines with a number of parallel processors that increases over time may not be, and in particular I don't know of any way to do this with the two models that you describe. Deco 15:17, 2 January 2007 (UTC)
Thanks! Just one more note, I think it is not important that there are a fixed number of CPU's, but only that the maximum number of CPU's in use, at any one time, in relation to the problem size is exponential, and therefore no polynomial simulation on a universal Turing machine can be made. So while my machine may be deterministic (not DTM just D) and massively parallel it is not Turing equivalent, and therefore not relevant. --ANONYMOUS COWARD0xC0DE 08:01, 3 January 2007 (UTC)
Well, it's Turing equivalent, it's just that a straightforward simulation by a DTM requires exponential slowdown, such that the DTM would require exponential time where the model takes polytime. If P=NP then it could simulate it in less time. But that sort of defeats the point. You're right that if the number of procs is polynomial then again the simulation is possible in polytime. Deco 12:19, 3 January 2007 (UTC)
Ok, I had a misconception (mistook capable of emulation for efficient (poly-time) emulation). So in essence my changes of if we had a polynomial time (and space) algorithm for C, we could solve all problems in NP in polynomial time (and space). could be stated as if we had a polynomial time algorithm (on a UTM) for C, we could solve all problems in NP in polynomial time. --ANONYMOUS COWARD0xC0DE 02:29, 10 January 2007 (UTC)

I take it back, PSPACE only means that the problem can be solved with poly-space algorithms, so this fact alone is not justification. For some reason I was thinking along the lines that any algorithm for a PSPACE problem must operate in polynomial space. --ANONYMOUS COWARD0xC0DE 12:18, 2 January 2007 (UTC)

[edit] With respect to other reductions headline

I feel that the section "With respect to other reductions", should be moved to the following page: http://en.wikipedia.org/wiki/Polynomial-time_many-one_reduction . I shall do that, if there are no objections.As the glorious weep (talk) 08:14, 19 November 2007 (UTC)

I believe that would be inappropriate. This is the correct place to discuss this, because it involves the class NP-complete and its definition, rather than reductions in general. Why would you want to move it? Dcoetzee 07:56, 19 November 2007 (UTC)
This section does not seem to fit into this particular article. Perhaps it is not well integrated. As the glorious weep (talk) 08:22, 19 November 2007 (UTC)

[edit] Things that must be added to this page

1. briefly discuss that the encoding of the problem can have an impact on the evaluation of complexity. In such cases, the most concise encoding should be used. This could answer ANONYMOUS COWARD0xC0DE, question, as I believe this is what he's talking about. page 974 of Introduction to Algorithms,second edition, Cormen, Leiserson, rivest

2. Need to clarify why "To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A."

3. We should clarify why having a polynomial time solution to 1 NP-complete problems causes the whole thing to collapse

4. Perhaps mention that NP problems are the problems that can be solved on a non-deterministic turing machine in polynomial time.

5. Talk about NP-complete problems being considered less tractable than P problems, and why. —Preceding unsigned comment added by As the glorious weep (talk • contribs) 08:10, 19 November 2007 (UTC)As the glorious weep (talk) 08:15, 19 November 2007 (UTC)

[edit] Rename page to NP-Completeness?

Per WP:MOS, "article titles generally comprise nouns or noun phrases." NP-complete is an adjective. NP-completeness is the noun form. Oren0 (talk) 18:11, 28 November 2007 (UTC)

Nope. "NP-complete" is the name of a complexity class, and so is a noun phrase. Dcoetzee 19:21, 28 November 2007 (UTC)
I would also rename it into NP-completeness. "NP-complete" is generally not used as the name of a complexity class but clearly as an adjective. ylloh (talk) 13:01, 29 November 2007 (UTC)
It's frequently used as the name of a class, on Complexity Zoo and in many papers. This is also the established naming scheme on Wikipedia (see P-complete, Sharp P complete, EXPTIME-complete). It's true that it's used more often in the adjective form, but that doesn't make the noun form an illegitimate name. Dcoetzee 23:05, 29 November 2007 (UTC)
Even if it can be used as a noun phrase, that's not how the article uses it. The lead needs to be rewritten if we're meaning NP-complete to refer to a class. Read P-complete's lead: "In complexity theory, the complexity class P-complete is..." Note that P-complete is used as a noun. Compare that to the lead of this page: "In complexity theory, the NP-complete problems are..." Here, NP-complete is used as an adjective. If indeed the article is supposed to be about the class, the lead should look like P-complete's IMO. Oren0 20:12, 3 December 2007 (UTC)
Agreed. Fixed. Dcoetzee 21:12, 3 December 2007 (UTC)