Better, Simpler Programming Contest

Saber Cherry · #1 March 3rd, 2004, 05:03 AM

I get confused about the difference between NP-Hard and NP-Complete. But generally, minSAT-type problems are NP-hard.

Anyway, I did a google search to clear up my confusion...

http://en.wikipedia.org/wiki/Computa...plexity_theory

I sort of recall that "NP-Complete" problems have to have a yes or no answer, and NP-Hard problems can have any answer. So a minimization/maximization that could be rephrased as NP-complete by asking "Is there a solution that scores above 100?" would itself be NP-hard.

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

[ March 03, 2004, 03:05: Message edited by: Saber Cherry ]

Leif_- · #2 March 3rd, 2004, 05:13 AM

Quote:

Originally posted by mlepinski:

Which raises the question: Is the problem that Saber Cherry posed NP-Complete?

Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?

Saber Cherry · #3 March 3rd, 2004, 05:19 AM

Quote:

Originally posted by mlepinski:
Which raises the question: Is the problem that Saber Cherry posed NP-Complete?

It's clear to me that the problem is NP-Complete if you allow an arbitrary number of resource types (...) However, it is unclear to me whether the specific Dominions-inspired problem (with exactly three resources and the ability to buy many copies of the same unit) is NP-Complete.

That is, indeed, hard to say. There's a way to make it more difficult, BTW, that I was pondering... a "Combined Arms" bonus. The value of a unit would be based on the number you build, so that (for example) the first of any unit was worth 2x the normal value, the second was worth 3/2x the normal value, the third was worth 4/3 of the normal value, and so forth. Not only would this be good for an AI (which would not always produce the same 2 or 3 units), but I get the feeling that it would ensure the problem was NP and not P.

Saber Cherry · #4 March 3rd, 2004, 05:22 AM

Quote:

Originally posted by Leif_-:

quote:
Originally posted by mlepinski:

Which raises the question: Is the problem that Saber Cherry posed NP-Complete?

Well, isn't it just a variant of the knapsack problem, which is known to be NP-complete?

Hmmm.

It looks like a multidimensional variant of the unbounded knapsack problem. Adding the combined arms bonus would change that, though.

mlepinski · #5 March 3rd, 2004, 06:02 AM

Quote:

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 :->

LaFollet · #6 March 3rd, 2004, 07:37 AM

Ummm.... And here I thought this was a thread about a simple programming problem.... and yet I don't have a clue about half the stuff being said. :S

Oh well, I guess I'll just get back to solving the problem...

EDIT:
I think you're number in the example for Holy is way off... I've never come accross any province with 120 holy...

[ March 03, 2004, 06:02: Message edited by: LaFollet ]

Saber Cherry · #7 March 3rd, 2004, 08:28 AM

Quote:

Originally posted by LaFollet:
Ummm.... And here I thought this was a thread about a simple programming problem.... and yet I don't have a clue about half the stuff being said. :S

Oh well, I guess I'll just get back to solving the problem...

EDIT:
I think you're number in the example for Holy is way off... I've never come accross any province with 120 holy...

Ooops! Thanks for pointing that out, I corrected it. Holy was supposed to be "4"

And - Yay! Someone is working on the problem

...however, the number of votes is still listed as 2 for me, both people who won't participate...