I add a look at the partition problem, this problem is know as the Easiest hard problem since it is NP-complete and seems pretty easy.

From wikipedia on NP-complete:

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial time.

For NP-complete problems like the Boolean satisfiability problem (SAT) I see why the verification is made in polynomial time (you just test and get 0 or 1 ?) but in the partition problem, if their is no perfect partition (0 if total sum is pair or 1 if total sum is impair) I don't see how you can verify if your solution is the best in polynomial time ? I don't see how you can do it without testing all the other possibilities ? is it just because you can prove this problem to be equivalent to the SAT problem (1) or their is an explicit algorithm existing ?

Am I missing something ? If you can advice me good documentation about possible algorithm in polynomial time to verify a solution it would be perfect.

(1)In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the problem of determining whether a Boolean formula is satisfiable.

EDIT: An example

let's say I have a set.

If I find a perfect partition: OK it's easy to check that it is the best.

Now suppose, I find a partition whose difference is 28 and let imagine there is only one better possible partition.

According to the NP completeness of the problem is there an explicit polynomial algorithm to do it. But I don't see how to prove that my solution is the best one without testing all other possibilities.


NP completeness is defined for yes-no questions. An instance of the partition problem is a question of the form: given these sets does there exist a partition. This is proved to be NP complete. Questions of the form: given these sets and a positive integer k does there exist a partition into less than k sets are also decision problems (and are also NP complete by reduction to partition). Questions of the form: Given these sets what is the smallest (or largest) size of a partition is not a decision problem, and so cannot be NP complete or not NP complete. A question of that form can be NP-Hard


On page 3 of your second link to The Easiest Hard Problem in American Scientist, Brian Hayes says

If you are given a proposed perfect partition, however, you can easily verify its correctness in polynomial time. All you need to do is add up the two subsets and compare the sums, which takes time proportional to n.

There is nothing more to it than this. You cannot be sure of being able to check in polynomial time a bare assertion that a set has or does not have a perfect partition.

  • $\begingroup$ thanks, but That's not really my question. I know that for a perfect partition it's easy to test (it's either 1 or 0, just make the calculation) But when I have a solution that is not perfect, how do I know in polynomial time my solution is not THE solution ? I've edited the post $\endgroup$ – Ricky Bobby Jul 11 '11 at 14:26
  • 1
    $\begingroup$ You don't. This is the same as the case with SAT If the equation is not satisfiable, you cannot verify it in P time. The class of problems where the unsolvability is verifiable in P time is co-NP en.wikipedia.org/wiki/Co-NP $\endgroup$ – deinst Jul 11 '11 at 14:37
  • $\begingroup$ @deinst : thanks first, and I was wondering, for the travelling salesman problem (NP-complete too) how do you tell if the equation is satisfiable ? since it's a min ? $\endgroup$ – Ricky Bobby Jul 11 '11 at 14:43
  • 2
    $\begingroup$ The version of the TSP that is NP complete is of the form: Does there exist a tour with total length less than $k$. Given a tour you add up the lengths and compare the result with $k$. $\endgroup$ – deinst Jul 11 '11 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.