The class of all problems that can be solved in polynomial time on a non-deterministic computer (ie. infinite # of processors running infinite # of threads and taking no time to spawn a thread), but merely exponential or worse time on a deterministic computer (ie. all the ones you have handy).
Not quite...
Rigorous technical definitions:
P is the set of all problems that can be solved in polynomial time on a (deterministic) TuringMachine.
NP is the set of all problems that can be solved in polynomial time on a nondeterministic Turing machine (NDTM). Because deterministic TMs are a subset of NDTMs, P is a subset of NP.
A problem is NP-hard if an algorithm to solve it in (deterministic) polynomial time would make it possible to solve all NP problems in polynomial time. NP-complete is the class of problems which are both NP-hard and themselves members of NP.
Finally, any NP-complete problem can be solved by a TM in time no worse than O(2^p(n)), where p(n) is the number of steps used by an NDTM for the problem. This is possible by just simulating the NDTM.
An equivalent definition of NP is the set of problems for which a proposed solution can be verified or rejected in (deterministic) polynomial time.
I may be remembering this wrong, but I thought that a condition for NP completeness is that there exists a validation function which can determine in polynomial time that a given solution is a valid solution for an NPComplete problem. No? -- AnthonyLander
Having a validation function that runs in polynomial time is what the sentence above your question is talking about. For NP completeness, every other problem in NP must also be reducible (in polynomial time) to an instance of your problem. So yes, having a validation function is a necessary condition for NP completeness, but it is not sufficient. For example, the problem of factorization has such a validation function, but it's most likely not NP complete.
Thanks...I'll try reading *and paying attention* before I write again. <grin> --a.l.
So far no one's proved this set has any members, but popular opinion is it sure seems to have a slew.
Actually, there are quite a lot...
The real open problem is whether P == NP. That is, can all NP problems be solved in polynomial time? A single polynomial algorithm for any NpComplete problem would show that P is equal to NP. It seems very possible that no such algorithm exists (many modern ciphers actually rely on P != NP for their security), but no one has proven or disproven this.
Wouldn't that be all ''modern ciphers? They're implementable in a smallish amount of hardware. Reduce to satisfiability. (Are you sure you don't mean all public key algorithms? (Either reducing a number to prime factors, or inverse logs in a discrete field (not sure about the last one, something akin is Used in ElGamal?))
There are many known NP-complete problems. The first problem proven to be NP-complete was the satisfiability problem, which asks whether a statement in boolean logic can be made true by some combination of values for its variables. Since this was proved, a large number of other problems have been shown to be NP-complete, including:
QuantumComputers have a very restricted form of nondeterminism, but it doesn't have anything to do with the number of qubits. The problem is one of observability: when you look at a quantum register which is in a superposition of states, you only get one of those states, and you destroy the superposition in the process. Quantum computers have not been shown to be able to solve any NpComplete problem in polynomial time. They could be used to factor integers in polynomial time, but factorization is not known to be NpComplete.
If they are ever shown to solve any one NpComplete problem in polynomial time however, they could be used to solve any NpComplete problem: any NpComplete problem could be reduced to the solvable problem in polynomial time, and then solved.
If RogerPenrose's conjecture about the reduction of the quantum state is correct, then that would mean that there's a practical upper limit on the number of qubits one can have.
Ow. Ow. My head hurts. Ow.
Don't eat ice cream quickly while reading Wikly
Computer scientists will sometimes use "X-complete" to denote a problem whose solution would imply solution of all problems in some domain or class X.
For example: some researchers say that natural language processing is an "AiComplete" problem. That is, it will be solved (in their estimation) if and only if the entire problem of strong AI is solved. [Can someone please suggest a good reference on this view? Thank you. Jason Grossman --- http://luddite.cst.usyd.edu.au/~jason]
(This use is usually intended as humorous, e.g. KitchenSinkComplete.)
Why does everyone think that P = NP is so hard? It's easy.
P == NP if and only if P = 0 or N = 1. Simple algebra, really.
Whatever the agreed upon solution for P=NP is, if you can find it there is a $1Million dollar prize being offered (one of the Millennium Prizes - see http://www.math.usf.edu/~eclark/baez2000problems.html).
When confonted with some tedious programming problem, I will often dub it NpAnnoying?. Sadly, solving it does not solve all such problems.
That's because you got the analogy around backwards. If it is in the class of 'annoying' problems, it should be an Na problem. If it reduces to all others in a (subclass) of Na, it will be Na-complete. The holy grail is then to show how to solve an Na-complete problem in a reasonable amount of time, then automate it.
But NpAnnoying? is funnier. If we're serious about it though, NaComplete? doesn't really say it either. NpHard or NpComplete (or harder still, ExpTimeComplete? http://en2.wikipedia.org/wiki/EXPTIME-complete) are all sets of problems of a given complexity. How can we classify problems by annoyingness? It seems that certain annoying problems (e.g. text parsing) cease to be annoying or become much less annoying in a BetterProgrammingLanguage?. Would the IdealProgrammingLanguage make all annoying problems easy, or are some problems (e.g. UserInterface) intractably annoying? Not to belabour the point more than it has been (did you really think I needed an outline of what Np is? interesting); anyway if you think about it a bit more you will realise you can't define Na-complete without a rigorous definition of annoying (Although you might get away with Na). Anyway, it is stretching a bad analogy too far... but I find N-annoying "more" amusing (not very) than the cognitive dissonance in NpAnnoying? (what's the p for). YMM-obviously-V.
P == NP since around 1965, and will continue to be equal for quite a while (EndOfMooresLaw). That is, if you measure computation time in the correct unit, MooreYears. Now, about that Millennium Prize ... http://www.math.usf.edu/~eclark/baez2000problems.html - PeteProkopowicz
August 2010, An Indian senior researcher from HP published a proposed 100+ pages proof on P!=NP, although subsequently fatal flaws have been found in it (http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/).
CategoryJargon CategoryComplexity