patternMinor
If a solution to Partition is known to exist, can it be found in polynomial time?
Viewed 0 times
canpartitionpolynomialexisttimefoundknownsolution
Problem
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?
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?
Solution
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.)
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.)
Context
StackExchange Computer Science Q#133962, answer score: 3
Revisions (0)
No revisions yet.