3
$\begingroup$

We are given a set of $n$ numbers and want to know whether it can be partitioned to two sets with an equal sum.

To prove that an equal partition exists, it is sufficient to show a partition.

What is the shortest way to prove that an equal partition does NOT exist? Apparently the only way to prove it is to show all the partitions and show that they are not equal. Is there a shorter proof?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ If a universally applicable, polynomially verifiable certificate were available to certify negative instances of PARTITION (or, any other NP-complete problem), then we would have NP=co-NP which would be a massive breakthrough. Given that, it may be worth exploring methods that are either 1) super-polynomial in time complexity, or 2) not universally applicable (i.e.: only useful in some subset of cases). $\endgroup$
    – mhum
    Commented Jul 9, 2018 at 20:10
  • 1
    $\begingroup$ The paper Semantic versus syntactic cutting planes gives an unsolvable instance of subset sum which is provably hard to disprove in a particular proof system, cutting planes. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2018 at 23:08

1 Answer 1

Reset to default
7
$\begingroup$

The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that.

The partition problem is NP-complete. For a NP-complete problem, we have an efficient way to certify that the answer to the question is YES, but not necessarily any efficient way to certify that the answer is NO. If you find an efficient way to verify that the answer is NO (i.e., a polynomial-length proof that can be verified in polynomial time), then you have proven that the problem is in co-NP. If you prove that any NP-complete problem is in co-NP, then you have proven NP = co-NP. Currently, it is widely conjectured that NP $\ne$ co-NP. Assuming that conjecture is correct, there is no polynomial-length polynomially-verifiable proof that an equal partition does not exist.

Improve this answer
$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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