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)