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!

Launceston

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.

Eluviation

This has the same issue as Pascal's answer -- problems which are not in NP can be NP hard. For example, any problem in EXPTIME. – Colonnade

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.

Expurgate

Which recently published "proof" were you referring to? – Sniff

Answer 3

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

Phylloid

And the Wikipedia article cited by Billy ONeal describes how this is equivalent to polynomial time verifiability by a deterministic Turing machine. This is the more intuitive formulation, though not the one giving rise to the NP name. – Carmancarmarthen

Answer 4

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".

Td

Your definition of NP-Hard is incorrect -- Problems which are not in NP can be NP-Hard. Also, there are NP-Hard problems which are not NP-Complete. See chart – Colonnade

@Billy ONeal What did I say that sounded like I meant that a NP-Hard problem could only be a NP problem? I would like to fix it but I don't see where... Plus my definition of "NP-Complete" wouldn't make much sense, would it? – Td

I fixed it and changed downvote to upvote -- the implication was that problem Q was "as hard as all NP problems", rather than "at least as hard as all NP problems" -- without "at least" it was implying equivalence. – Colonnade

@PascalCuoq, Do you have any sources for your definition of NP? You say that "the verify the solution alternative definition has become popular recently", but from the sources I could find, that actually seems to be the original definition. – Sniff

@Sniff What sources have you found that seemed to imply that it was the original definition then? I would rather not spend my time digging up articles published in the last century, before the Internet, if I can avoid it. I believe that the name NP was chosen in reference to the “nondeterministic definition”. Why wasn't the class named “VP” if it was defined as the class of problems verifiable in polynomial time? – Td

@PascalCuoq, I don't have authoritative sources claiming the alt definition. However, it is as you've said, the "popular one" and it seems to be the status quo, thus justifying the need for citation if you are going to claim that another definition is the original one... – Sniff

@Sniff [1] Marianne Delorme, personal communication. Seriously, I don't have the time, as I said, but downvote my answer if you don't like it. Be sure to downvote any answer that does not appropriately explain why it is called N P when it is defined with respect to polynomial verification time. Or write your own answer that explains both things. I don't have to be involved. – Td

@PascalCuoq, Right, was just thinking you probably have it off the top of your head about where you've heard that definition. Yours is the first time I've seen someone mentioning "verify the solution" is not the (original) definition. – Sniff

Answer 5

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

Colonnade

++ for the "Complete" explanation – Launceston