Why are NP problems called that way (and NP-hard and NP-complete)?

Question

Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand. I realize that a solution for NP problem can be verfied in polynomial time. But what does determinism has to do with that?
And if you could explain me where NP-complete and NP-hard got their names, that would be great (I'm pretty sure I get the meaning of them, I just don't see what their names have to do with what they are).
Sorry if that's trivial, I just can't seem to get it (-:
Thanks all!

Answer 1

NP is called NP (nondeterministic polynomial time) because an NP problem can be solved in polynomial time by a nondeterministic turing machine.

Answer 2

But what does determinism has to do with that?

From Wikipedia:

NP is the set of all decision problems for which the 'yes'-answers have efficiently verifiable proofs of the fact that the answer is indeed 'yes'. More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine

Not sure about the history of the names though. EDIT: I have guesses though. What follows is speculation but I don't think it's unreasonable.

NP-Hard is any problem which is at least as hard as the hardest problems in NP. Therefore, it could be said that the problem in question would have NP hardness., hence NP-Hard.

If any single problem in NP-complete can be solved quickly, then every problem in NP can also be solved quickly. Therefore, the complete set of NP problems could be solved.

EDIT2: Wikipedia's Complete (Complexity) article indicates:

a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class

Answer 3

Let's begin with NP: in NP, N is for "nondeterministic" and P is for "polynomial time". It is the class of problems that can be solved in polynomial time if you have a nondeterministic Turing machine that can branch at each cycle to explore possibilities in parallel (the "verify the solution" alternative definition has become popular recently but it does not make clear what "N" means). The nondeterministic machine can be compared to a parallel computer with an infinite number of processors, and the ability to fork() at each instruction.

Saying that a problem Q is "NP-hard" means that any problem in NP can be reduced to problem Q (in polynomial time). Since the relation "can be reduced to" between problems is an order relation, you can think of "NP-hard" as meaning "at least as hard as all NP problems".

An "NP-complete" problem is simply one of the problems in NP that is NP-hard. I guess that class of problems needed a name, but I'm not sure how to explain the choice of the word "complete".

Answer 4

P

Class of all problems which can be solved by a deterministic Turing machine in polynomial time.

NP

Class of all problems which can be solved by a non-deterministic Turing machine in polynomial time (they can also be verified by a deterministic Turing machine in polynomial time.)

NP-Hard

A class of problems which are "at least as hard as the hardest problems in NP". Formally, a problem is in NP-Hard iff there is an NP-complete problem that is polynomial time Turing-reducible to it; (also: iff it can be solved in polynomial time by an oracle machine with an oracle for the problem). It is pretty obvious where the name comes from.

NPC

The class of problems which are both NP as well as NP-Hard. Regarding the naming, even wikipedia is not sure why it's named as it is.

Answer 5

Let's start with "nondeterministic". A deterministic machine can be in one state at a time. We can actually make them. A nondeterministic machine is a theoretical construct that can be in more than one state at a time. (There's similarities to quantum computing here, but for our purposes here they're misleading. Disregard them.)

If we want to solve a problem with a deterministic machine, we start it up, and it goes through a series of steps to try to find a problem. If we model using a nondeterministic machine, it can go through all possible series of steps at the same time.

The set of problems we're going to be concerned with is decision problems: given a problem statement, either there is a solution or not. Find a solution or report that there is none. For example, assume you have a set of logical statements: A or not-B, B or C or D, not-D or A or B, .... Given an arbitrary set, can you find truth values for all the variables such that all the statements are true?

Now, let's consider the P. Suppose we represent the size of a problem by n. The size could be the number of cities in a traveling salesman problem, the number of logical statements in the problem above, whatever. Given a certain n, the problem will require a certain amount of resources to solve on a given system. Now, if we double the resources or computational ability, what happens to the size of the problem we can solve? If the problem is of polynomial complexity, which means in P, the size goes up by a certain fraction. It might double, or go up by 40%, or 10%. In contrast, if it's of exponential complexity, the size goes up by a certain number. We generally think of P problems as solvable and exponential problems as unsolvable as the problems get large, although that's a simplification. From an informal point of view, polynomial complexity is being able to figure things out about the problem sequentially, while exponential is having to look at all possible combinations.

Suppose we can solve the problem in polynomial time on a deterministic machine. The problem is in P. Suppose we can solve it in polynomial time on a nondeterministic machine, which is the same thing as being able to verify a proposed solution in polynomial time on a deterministic machine. Then the problem is in NP. The trick here is that we can't make true nondeterministic machines, so that the fact that a problem is in NP doesn't mean it's practical to solve.

Now on to NP-complete. All problems in P are in NP. For problems A and B in NP, we might be able to say that if A is in P, so is B. This is done by finding a way to restate B as an A sort of problem. An NP-complete problem is one such that, if it is in P, every problem in NP is in P. As you might guess, finding a way to restate every possible problem as one particular one wasn't easy, and I'll just say that the problem with logical statements above (the Satisfiability problem) was the first proved NP-complete. After that it was easier, since it was only necessary to prove that if problem C was in P, so was Satisfiability.

It's generally believed that there are problems that are in NP but not P, and a proof was recently published (which may or may not turn out to be valid). In that case, NP-complete programs are the hardest sorts of problems in NP.

There are problems that don't fit into this mold. The Traveling Salesman Problem, as normally posed, is to find the cheapest route connecting all cities. That isn't a decision problem, and we can't verify any proposed solution directly. We can restate it as a decision problem: given a cost C, is there a route that's cheaper than C? This problem is NP-complete, and with a little work we can solve the original TSP about as easily as the modified, NP-complete, form. Therefore, the TSP is NP-hard, since it's at least as hard as an NP-complete problem.