Talk:NP (complexity)

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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.