[mlepinski]

Originally posted by Saber Cherry:

It confuses me since I've been told contradictory facts:

NP-C must have a yes or no answer.
NP-H can have any answer.
NP-H is a subset of NP-C.

So I was trying to avoid confusion by saying "NP", but that failed=)

Incidentally, according to that site, Class P is the set of problems solvable in polynomial time, and Class NP is a set of problems that are probably not in Class P. To quote it:

quote:

---

In complexity theory, the NP-complete problems are the hardest problems in NP, in the sense that they are the ones most likely not to be in P.

Thus... I think it is correct to call an NP-C problem "NP". But then, it's just some random internet site

---

I apologize for diverting this thread into a discussion of computational complexity, but I'd like to remind everyone that Phil started it. :->

In any case, the wording on the website you reference is a bit confusing, so hopefully this will help clear up the confusion.

P is the class of (decision) problems solvable in polynomial time by a deterministic (i.e., ordinary) computer.

NP is the class of (decision) problems that are solvable in polynomial time by a non-deterministic computer. (The best way to think about NP is as problems who's answer can be checked in polynomial time.)

Every problem in P is also in NP but it is widely believed that there are problems in NP that are not in P.

NP-Complete are the hardest problems in NP. In particular, if an efficient (deterministic polynomial time) solution were found to any NP-Complete problem, then P = NP.

Every NP-Complete problem is in NP. Therefore, every NP-Complete problem is a decision (Yes/No) problem.

A Problem is NP-Hard if it is at least as hard as every problem in NP. That is, a problem is NP-Hard if solving said problem allows one to solve every problem in NP. (If there is an efficient solution to any NP-Hard problem then P=NP).

NP-Hard problems can be decision problems but they don't have to be. Every NP-Complete problem is also NP-Hard.

So technically, the optimization problem that Saber Cherry proposed can't be NP-Complete because it's not a decision problem. However, one can easily transform any optimization problem into an equivilant decision problem. For instance, instead of asking to maximize value, you can ask, "Is it possible to achieve a value of k?" (which is a decision problem). This is equivalent to the optimization problem because if you had an efficient program to solve the decision problem, you could run it many times (using a binary search) to find the optimal value of k. That is, (assume M is some big number larger than the maximum possible value) you could first run the program to find out if it's possible to achieve M/2. If it is possible to achieve M/2 then you run the program for 3*M/4. If 3*M/4 isn't achievable you would try 5*M/8. (In the worst case this requires running the decision program log(M) times which is polynomial in the size of your problem instance).

Hopefully the above explaination made some things more clear. (I apologize if my earlier post caused some confusion, what I really meant was "Is the decision Version of the optimization problem NP-Complete").

Also, thanks a lot for the unbounded Knapsack link. (I'm not familiar with the proof that unbounded Knapsack is NP-Hard, but I will undoubtably spend time tossing and turning in my bed tonight trying to figure out why this true ).

- Matt Lepinski :->