# If a solution to Partition is known to exist, can it be found in polynomial time?

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?

• 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. – user53923 Jan 4 at 14:18
• The first argument shows that if P≠NP then GuaranteedPartition cannot be solved in polynomial time. – Yuval Filmus Jan 4 at 14:39
• @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. – Erel Segal-Halevi Jan 4 at 19:09
• 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. – Yuval Filmus Jan 4 at 19:11