Np Complete

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.

Okay ... so you're saying there are, at least conceptually, problems that are NP-Hard but not NP-complete? What kinds of beasts are they?
NP-hard problems are at least as hard as NP-complete ones. Consider this problem: solve every minimal graph-coloring problem of size n. Clearly, solving this problem in polynomial time would also allow one to solve the NpComplete minimal graph-coloring problem (and thus all NP problems) polynomially. However, the problem given is not itself a member of NP (it is too hard), so it is NP-hard but not NpComplete.
The distinction can be made (even?) clearer by pointing out that the HaltingProblem is NP-hard. Certainly it's the case that if you have a program that can solve the HP in polynomial time, you can solve any NP-complete problem in polynomial time. Of course, you could also grow wings and build a perpetual motion machine if you had such a program. --AnonymousDonor

NP-complete problems have the property that any one of them can be reduced to any other in polynomial time. Thus if I can solve NpComplete problem A in polynomial time, I can also solve NpComplete problem B in polynomial time by first converting it to an equivalent instance of problem A in polynomial time, and then solving that problem. (Also, to prove that a problem is NP-complete, it is sufficient to show that it is polynomial-time equivalent to some other NP-complete problem.)

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:

Three-Satisfiability (satisfiability restricted to formulas in conjunctive normal form with three variables per clause)
Integer linear programming
Minimum graph coloring
Hamiltonian circuit
MaximumClique
TravelingSalesmanProblem
Minimum multiprocessor scheduling
Shortest common superstring
Training a neural network

The canonical encyclopedia of NP-complete problems is Garey and Johnson, "Computers and Intractability: A Guide to the Theory of NP-completeness"

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