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

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 2

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.