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 ]