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?

Improve this question
$\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$ Commented Jan 4, 2021 at 14:18
  • $\begingroup$ The first argument shows that if P≠NP then GuaranteedPartition cannot be solved in polynomial time. $\endgroup$ Commented Jan 4, 2021 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$ Commented Jan 4, 2021 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$ Commented Jan 4, 2021 at 19:11

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ This clarifies the issue. Thanks! $\endgroup$ Commented Jan 5, 2021 at 17:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.