Talk:NP (complexity)

Simpler Algorithm

on long factorial(int n) {0p

  result = 1;
  while (n != 0) {
     result = result * n;
     n = n - 1;
  }
  return result;

}

Introductory example

Is it best to open this article with an example of a challenging problem that is in P but not NP-complete? Composite/primality testing is in P; while the article hints at this, the reader is left a bit muddled as to the distinction between P and NP. -Czyl

I chose this example because it's particularly simple, and can generally rely on a basic math background, unlike satisfiability or graph colouring. Factoring is accessible, but again a little more complicated. It's a tradeoff. Deco 22:05, 30 August 2005 (UTC)

Can somebody fix this syntax? "All problems in NP have a deterministic function just like this, which accepts only when given both an input and proof that the input is in the language." I'm having trouble accepting "accepts" as an intransitive verb. Rsmoore 05:15, 28 March 2006 (UTC)

It is standard terminology in the literature. It is understood that machines act on their inputs. Think of accepts as short for 'goes to an accepting state'. Arvindn 05:52, 28 March 2006 (UTC)

"Nondeterministic machine branching into n different paths in just O(log n) steps" sounds wrong to me - isn't the point of nondeterminism that branching is free? 89.102.137.191 20:01, 10 July 2006 (UTC)

Nondeterministic Turing machines at least can only branch a fixed number of ways in each time step. Other models of nondeterministic machines might not have this limitation. Deco 20:19, 10 July 2006 (UTC)

Is the example in "Introduction and application" correct? I see a contradiction in the following statements from different wikipedia pages:

* http://en.wikipedia.org/wiki/Composite_number
* (1) By definition, every integer greater than one is either a prime number or a composite number.

* http://en.wikipedia.org/wiki/NP_%28complexity%29 (this is the example I'm concerned about)
* (2) As an example, consider the problem of determining whether a number n is a composite number.
  For large numbers, this seems like a very difficult problem to solve efficiently.

* http://en.wikipedia.org/wiki/Primality_testing
* (3) As of 2007, factorization is a computationally hard problem, whereas primality testing is comparatively easy.

(1) and (3) => testing if a number is composite is as easy as testing if it's prime, which is in contradiction with (2). But it's possible that I'm just missing something. Inetic 23:38, 21 March 2007 (UTC)

Indeed, the section as I found it today doesn't seem to make any point at all and can't make up its mind whether primality testing is in NP or not and whether NP problems have polynomial-time solutions or not and whether polynomial-time and efficient are the same thing. I have rewritten it so all this is clear and it makes a point, but I'm not sure it's a 'valid' point. In particular, the goal of the section seems to be to say what "the challenge of NP problems is," and I'm not sure I know what challenge the author was thinking of. Maybe it's supposed to be the challenge of proving a problem 'is' in NP. Bryan Henderson 16:58, 21 June 2007 (UTC)

I also don't like this approach. "Primality testing is in P. Now we'll prove that it's in NP." It's not that it's incorrect, it just feels strange. It would be more satisfying if primality testing was first proven to be in NP, and then a simple statement "In fact, primality testing has been proven to be in P as well, but only recently and it is much more difficult" or something to that effect. And it would be much more satisfying to introduce the subject with an example that isn't proven to be in P, such as an NP-complete problem. What about factorization? It shouldn't be too hard to demonstrate how verifying a factorization is in P, should it? -- Jao 20:00, 17 July 2007 (UTC)

Factorization is not NP-complete, although not known to be in P. On the P and NP page they settled on the subset sum problem. Dcoetzee 20:10, 17 July 2007 (UTC)

Thanks for briefing me on the status of factorization. As it didn't really matter here whether it was NP-complete or not, I hadn't researched it. Anyway, any NP problem not known to be in P would do, and the subset sum problem looks like a good example. -- Jao 20:38, 17 July 2007 (UTC)

The current description is wrong...

The latest edits to this page (made on June 21, 2007 at 16:51) are wrong. "Composite" is not NP-Complete. Many other edits are also incorrect (use of the term "machine" is more appropriate than "algorithm"). I am going to try to revert it back to the older version (if I can figure out how).

A.

Decision problem

After reading the article it's unclear to me whether an NP problem must be a decision problem. The lead says NP contains all decision problems...; but does it also contain other stuff? The examples include finding a number which (nontrivially) divides a given number, which isn't a decision problem, but the rest of the article implies that it should be. If an NP problem must be a decision problem, then perhaps contains could be changed to consists of, and the factoring example changed to whether a given number is composite (or just removed). --catslash (talk) 18:43, 11 October 2008 (UTC)

An NP problem must be a decision problem. The "contains" statement was meant to imply "contains and only contains". The factoring example was just plain incorrect (the correct decision problem is not whether a number is prime, which is in P, but a bit more complicated, see my edit). Dcoetzee 19:16, 11 October 2008 (UTC)

Thanks for clarifying that. The contains usage I'm not familiar with, so I'll change it to the is the set of - just revert it if this is not accurate. --catslash (talk) 20:09, 11 October 2008 (UTC)

I have a similar problem: In the Verifier-based definition the "subset sum problem" example is mentioned. While i find the example easy to understand, it is again in contradiction to the definition that NP is the set of all decision problems for which the 'yes'-answers have simple proofs of the fact that the answer is indeed 'yes'. In the example a given subset is verified to equal zero. However, I fail to see how a positively terminating non-deterministic Turing machine could be verified. —Preceding unsigned comment added by 131.220.99.58 (talk) 15:09, 10 February 2010 (UTC)

Travelling salesman

The decision problem of travelling salesman is said here to be in NP, but on the travelling salesman page, said to be NP-complete. —Preceding unsigned comment added by 138.16.19.86 (talk) 19:07, 9 November 2008 (UTC)

Every NP-complete problem is in NP. Blokhead (talk) 20:09, 9 November 2008 (UTC)

The current definition is possibly wrong

A mistake in the text:

I think "In an equivalent formal definition, NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." (located in the introduction) has to be "NP is the set of decision problems for which a yes answer can be checked in polynomial time" . According to me it has to be like that otherwise there wouldn't be a difference with P, which is a subset op NP. The possibility that P=NP hasn't been proven yet.

Kind regards —Preceding unsigned comment added by BVDC (talk • contribs) 14:47, 6 December 2008 (UTC)

It's correct, and so is your definition. The two are equivalent and this is explained in detail later on in the article. The key is the word "non-deterministic" - a non-deterministic Turing machine is different from a deterministic (ordinary) Turing machine. Dcoetzee 17:05, 6 December 2008 (UTC)

Connection to Search Problems

I think this page should also cite the connection to search problems, since in practice many problems are formulated as search problems. Then, we can add that the search problem for an NP-complete decision problem is polytime-reducable to the decision problem, and if P=NP then every associated search problem is solvable in polynomial time. 85.124.63.18 (talk) 12:38, 23 February 2009 (UTC)

This is already covered by the statement that P=NP if and only if FP=FNP, which is discussed in P = NP problem. Dcoetzee 18:53, 23 February 2009 (UTC)

P subset of NP

User:Oddity- added a to the statement that NP contains "all problems in P". So I've added an explanation there, but feel free to remove it if you think it's badly written or that the fact doesn't need an explanation. Regards, Shreevatsa (talk) 23:27, 18 March 2009 (UTC)

Mistake in definition

There might be a mistake in definition of NP class. Article claims:

"In an equivalent formal definition, NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine."

However according to definition from this article http://en.wikipedia.org/wiki/Decision_problem

A decision problem A is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set.

the definition should be:

"In an equivalent formal definition, NP is the set of decision problems effectively solvable in polynomial time by a non-deterministic Turing machine."

It is because the decision problem must be effectively solvable (decidable) by non-deterministic turing machine to be in NP class, in other words decision problem must be recursive set and not recursively enumerable set. —Preceding unsigned comment added by 77.48.31.4 (talk) 15:28, 11 May 2009 (UTC)

In the context of computational complexity, all machines are assumed to always terminate. Hence this ambiguity does not arise. In an introductory article that may bear emphasizing, to avoid confusing people coming from computability theory, but on the other hand that would also confuse people with no background in computability theory. Dcoetzee 07:47, 12 May 2009 (UTC)

Well yes, I came with some computability theory background and it confused me a bit. At least clarification now can be found here in discussion... —Preceding unsigned comment added by 141.202.248.68 (talk) 13:56, 12 May 2009 (UTC)

If it is 'solvable in polynomial time by a non-deterministic Turing machine, then it is effectively solvable in polynomial time by a non-deterministic Turing machine, by having a UTM run it for polynomially many steps, after which if the original machine hasn't given an answer, the UTM gives the answer "no".

JumpDiscont (talk) 16:48, 20 July 2010 (UTC)

The definition of NP belongs to Levin and Cook. This must be mentioned. 72.166.11.101 (talk) 06:10, 11 June 2011 (UTC)

I still don't see how this definition can be the right one - surely NP doesn't require that the decision problem can be solved in polynomial time in all cases (as implied by the definition as currently stated), but only in the "yes" cases? --Kotniski (talk) 09:00, 25 November 2011 (UTC)

I guess the confusion is about what it means for a non-deterministic machine to solve a decision problem. A non-deterministic machine non-deterministically chooses computation paths, so at the end of the computation there are many possible computation paths. A non-deterministic machine is said to solve a decision problem if, when the instance is a yes instance at least one computation path accepts, and when it is a no instance none of the paths accept. Now I think it is accurate to say that NP is the set of decision problems decidable in polynomial time by a non-deterministic Turing machine. --Robin (talk) 04:05, 30 November 2011 (UTC)

I still don't think so (and it certainly isn't intuitive to use this language) - you only have the solution in polynomial time if one of the paths accepts. If none of the paths accept, you've "decided" the problem, but not in polynomial time (or necessarily in any kind of time).--Kotniski (talk) 07:18, 30 November 2011 (UTC)

Each path terminates in polynomial time, and at the end announces whether the path has accepted or rejected. An NP machine is said to accept if any of the paths accepts. It is said to reject if all of the paths reject. It is said to run in polynomial time if all paths terminate in polynomial time. Does that sound more intuitive? --Robin (talk) 18:33, 1 December 2011 (UTC)

A bit, but it doesn't give a full explanation like that in the article, so I still think the wording is misleading and needs to be clarified for the semi-informed reader.--Kotniski (talk) 06:45, 2 December 2011 (UTC)

I mean, the definition you've restored says that the problem is "decidable in polynomial time by a non-deterministic machine..." We could at least say (in line with the wording you've just used) that it's "decidable by a non-deterministic machine that runs in polynomial time..." Acceptable?--Kotniski (talk) 06:48, 2 December 2011 (UTC)

Yeah, sure. Both sentences mean the same thing to me, but I can see why you feel that the second one might be clearer. --Robin (talk) 15:39, 3 December 2011 (UTC)

I inserted this wording, then, but added a bracketed explanation since it still won't be clear to many. The same confusion (possibly about substance rather than wording) seems to have arisen at NTIME; I've started a thread at User talk:129.104.247.2 to try to resolve it.--Kotniski (talk) 12:07, 6 December 2011 (UTC)

In in the name of holy heck is this about. It seems like the only people who are going to understand this are those who already know what it means. Surely your expertise should enable the authoring of an article that is useful to someone who does not have a masters in...well I'm not even sure what the discipline is. — Preceding unsigned comment added by 203.167.234.102 (talk) 23:01, 13 February 2012 (UTC)

Relation to MA

Isn't the current explanation of the relationship between NP and MA wrong as stated? It says "no communication from Merlin to Arthur". Shouldn't it say "no communication from Arthur to Merlin"? If Merlin doesn't communicate to Arthur then you just have BPP, right? — Preceding unsigned comment added by 165.91.14.139 (talk) 21:09, 21 February 2012 (UTC)

(Over 3 years later,) I fixed that problem. JumpDiscont (talk) 10:40, 2 July 2015 (UTC)

Incorrect formal definition?

The formal definition of the article states: For all x and y, the machine M runs in time p(|x|) on input (x,y)

I'm not an expert in the field but this leads to think that M must run in time p(|x|) regardless of the size of y, which doesn't seem to be true, at least if M reads y completely. What if |y| > p(|x|)?

I don't know if the article's definition is incorrect (it seems it is) but at least I think it's worth clarifying. Actually, in this respect I can quote "COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP-Completeness" by Michael R. Garey / David S. Johnson. In their definition of NP base on deterministic verifiers (very similar to the one in the article) they state (on page 29):

"Notice that this has the effect of imposing a polynomial bound on the size of the quessed structure S [y in the article], since only a polynomially bounded amount of time can be spent examining that guess."

Should we modify the definition to "For all x and y, the machine M runs in time p(|x|+|y|) on input (x,y)" or at least add a clarification similar to the one in the book I quoted?

83.226.144.206 (talk) 23:32, 22 March 2014 (UTC)

I would "second" that the formal definition needs work. Specifically, it needs a citation. The problem is that there is no description of what "M" is doing - it's verifying a claim that y is a string in language x. We need a citation here.

two-dimensional euclidean TSP is a bad example

The section called Why some NP Complete problems are hard to solve contains the text Also, the real life applications of some problems are easier than their theoretical equivalents. For example, inputs to the general Travelling salesman problem need not obey the triangle inequality, unlike real road networks..

This is a bad example; two-dimensional euclidean TSP is still NP-complete. I strongly doubt that general two-dimensional euclidean TSP is easier than general TSP in any way which we can formalize. Furthermore, two-dimensional euclidean TSP could itself be considered a rather theoretical problem, because it is widely studied in the literature and it is probably of little use in most practical applications without significant adaptation.

I do not know of a better example off the top of my head, but I would rather have no example here than an example which is so misleading that it borders on being factually incorrect. Would anyone object if I removed the second sentence of the above quote from the article? Wikiedit738 (talk) 09:05, 8 April 2015 (UTC)

Possible Ultimate Definition

If it is of interest to discuss, here you can read some demonstrations solving the relationship between P, NP and #P

http://rekpub.com/American%20Open%20Computer%20Science%20Journal/Current%20Issue.php — Preceding unsigned comment added by JuanManuelDato (talk • contribs) 12:06, 23 August 2015 (UTC)

Introduction confusion

I see from previous comments that the intro has been hashed over several times already. However, at the current time, it still doesn't get across a clear idea of the criteria for problems described as NP.

It gives one definition:

"NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs [... that is] verifiable in polynomial time by a deterministic Turing machine."

This may be true, but doesn't indicate why "NON-deterministic" is part of the name of this set.

The intro's second definition:

"NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine."

... seems to throw the first definition into doubt. If an NDTM is required to accept (verify) yes answers (in poly time), then the first definition seems wrong.

I would like to see a description that simply explains the concept by starting with the name of this complexity class:

NP: Nondeterministic, Polynomial time" [Note the comma, I'm pretty sure we're not talking about nondeterminism of polynomial time.]

"A class of decision problems for which a Nondeterministic Turing Machine can do [something] within polynomial time."

Now, what is the [something]?

Verify a solution, so long as it's a yes? Determine whether a proposed solution is a yes or no? Or? I'm hoping someone will spell this out. In less than polynomial time :-).

Gwideman (talk) 21:43, 28 October 2015 (UTC)

I agree it doesn't make sense. I think the second definition in the introduction is wrong. A NDTM can "solve" NP problems in poly time, not just "accept" yes-instances. This is corroborated in the body of the article under "machine definition". I will try to correct the intro but I would appreciate it if someone can verify this. Ajnosek (talk) 16:36, 18 July 2016 (UTC)

Lack of History and Meta-Encyclopedic Information

This article may benefit from a paragraph on the history of the problem, including a summary of the major research conveying the lineage of researchers as well. For example the researcher Ladner is mentioned in the diagram caption, but there is no mention in the article body and little mention of anyone else, or how and why the problem was discovered and evolved academically.

While all of those things are probably covered in other complexity theory articles, and taking under consideration there may be repetition between this article and NP-hard, NP-complete, etc when it comes to meta information: it still seems NP is central enough not only to theory, but practical computing itself, warranting a little more than just a technical lecture. — Preceding unsigned comment added by Jasonzemos (talk • contribs) 17:59, 5 December 2016 (UTC)

Possible issue with definition, again

The article says at the top: "...have proofs verifiable in polynomial time by a nondeterministic Turing machine". Shouldn't the verifiable bit be doable even by a *deterministic* (no-non) one? -->— Preceding unsigned comment added by 31.205.55.139 (talk • contribs) 01:15, 14 May 2021 (UTC)

Yeah, that's correct; I'll fix it in a jiffy. NP problems are those that can be *solved* by nondeterministic Turing machines, but verified by *deterministic* Turing machines. (The current definition is actually defining NP^NP, the second level of the polynomial hierarchy). By the way, I manually signed your comment for you, but you should sign your comments in the future (which you can do by typing four tildes in a row). Duckmather (talk) 03:53, 14 May 2021 (UTC)

Verifiable in non-deterministic polynomial time

Google search also shows definitions of NP as "verifiable in nondeterministic polynomial time".

That variant of the definition is missing in this article.

Is this (third) variant of definition of NP correct? If yes, add it with a reliable authoritative citation! --VictorPorton (talk) 14:03, 4 July 2021 (UTC)

It seems that the definition "verifiable in nondeterministic polynomial time" is wrong, because it would imply that a problem verifiable by another algorithm in NP would be itself in NP. But that would imply that every P problem is NP, because an NP algorithm could be verified by itself! Note that Wolfram's MathWorld does contain this (apparent) error. We should refer to such sources (including MathWorld) with the note that they have an error, as I understand. --VictorPorton (talk) 14:11, 4 July 2021 (UTC)

The variant is correct (if properly defined), and there are different ways to explain it; for me the most natural is to understand verification as defined in the main article. Now, allowing the verifier to be deterministic is equivalent to making it deterministic while providing it with an additional witness $y'$ to replace the non-deterministic choices. This witness is of polynomial size (in $x$) and so the new algorithm falls under the currently given definition. I am not aware of a source I could cite, so I'm not adding this to the article. AmirOnWiki (talk) 08:27, 24 July 2021 (UTC)

References to nondeterministic Turing machines in the introduction

I edited a reference to nondeterministic algorithm (as in computer programming) in a context where it actually refers to nondeterministic Turing machine, but I undid it since I realized that there are already two references to nondeterministic TMs in the introduction.

I'm not sure what are the guidelines around that, but shouldn't we use a reference only in the first instance? Also, maybe the reference to nondeterministic algorithm should be removed? Eduardogbg (talk) 18:09, 18 August 2023 (UTC)