3
$\begingroup$

In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.

Suppose we are given an instance and we know that it admits an equal-sum partition. Can this partition be found in polynomial time (assuming $P\neq NP$)?

Let's call this problem "GuaranteedPartition". On one hand, apparently one can prove that GuaranteedPartition is NP-hard, by reduction from Partition: if we could solve GuaranteedPartition with $n$ numbers in $T(n)$ steps, where $T(n)$ is a polynomial function, then we could give it as input any instance of Partition and stop it after $T(n)$ steps: if it returns an equal-sum partition the answer is "yes", otherwise the answer is "no".

On the other hand, the GuaranteedPartition is apparently in the class TFNP, whose relation to NP is currently not known.

Which of the above arguments (if any) is correct, and what is known about the GuaranteedPartition problem?

$\endgroup$
4
  • $\begingroup$ You should probably be clearer about what you mean by NP-hard. Under the definition "NP-hard under Karp reductions" it should be obvious that GuaranteedPartition cannot be NP-hard (as is explained on the wikipedia page you linked). But indeed, if GuaranteedPartition is in P, so is Partition, as you correctly argue. $\endgroup$ – user53923 Jan 4 at 14:18
  • $\begingroup$ The first argument shows that if P≠NP then GuaranteedPartition cannot be solved in polynomial time. $\endgroup$ – Yuval Filmus Jan 4 at 14:39
  • $\begingroup$ @YuvalFilmus Suppose we have an algorithm that solves GuaranteedPartition correctly when an equal partition exists, but when an equal partition does not exist, its behavior is undefined (as in the C++ standard en.cppreference.com/w/cpp/language/ub ). Then I am not sure the first argument works. I am also unsure if the concept of "undefined behavior" makes sense at all. This is quite confusing. $\endgroup$ – Erel Segal-Halevi Jan 4 at 19:09
  • $\begingroup$ We don’t care what the algorithm does. If it doesn’t output a valid partition after the allotted time, we know that no such partition exists. $\endgroup$ – Yuval Filmus Jan 4 at 19:11
3
$\begingroup$

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different from a promise, which is more like what you're describing.

Unlike integers and factorizations, there are sets that do not have equal-sum partitions. And if you change the input format to be some strange representation of sets of integers such that every set represented always has a valid partition, then you change the problem entirely. A program that solves this new problem probably couldn't be used to solve the original NP-hard Partition problem.

(GuaranteedPartition is also not a decision problem, so it's not NP-hard either - although a machine that solved GuaranteedPartition could be used to solve anything in NP, as you point out.)

$\endgroup$
1
  • $\begingroup$ This clarifies the issue. Thanks! $\endgroup$ – Erel Segal-Halevi Jan 5 at 17:41

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.