Talk:NP (complexity)
From Wikipedia, the free encyclopedia
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)
