2
$\begingroup$

The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$?

I have read a lot of proofs using the Subset Sum problem: Given an integer set $S$ and an integer t, does there exist a subset $U$ of $S$ such that $\sum_{s \in U}s = t$? My problem is that most of them does not consider that the partition problem does not require the inputs to be integers, and a lot of them transform the input $S$ of the Subset Sum problem to $S\cup \{ \text{some elements} \}$ in the Partition Problem. If the input to the partition problem is non-integer, or, worse, irrational, I do not think this method works.

I have tried to reduce the partition problem to subset sum problem, by transforming the input $S$(which could be irrational numbers) to $S^{\prime} = \{ 2\lceil s_{i} \rceil \}$ and $t = \sum_{i} \lceil s_{i} \rceil$. Besides, I have also tried a few other similar ways including considering the floor function. However, whichever I tried, I could not prove that partition problem has a solution on $S$ if and only if the subset sum problem has a solution on $(S^{\prime},t)$. I do not find any contradiction if the subset sum problem has a solution on $(S^{\prime},t)$ and the partition problem does not have a solution on $S$, and vice versa. It sort of makes sense to me because having the result in integer subset sum problem could hardly have any implications on the non-integer partition problem.

Would anyone have any hints on how to prove the non-integer version of the Partition Problem is NP-complete by reducing it to the Subset Sum Problem?

Improve this question
$\endgroup$
5
  • $\begingroup$ Are sure that you have to reduce it to the integers subset sum problem? Because integer and irrational problems are usually modeled in different models of computation. (e.g. you can't give a Turing machine computing the square root $\pi$ as input cause the description would be infinite) $\endgroup$
    – plshelp
    Oct 12, 2020 at 15:28
  • $\begingroup$ @plshelp I just wonder if it is really possible to prove that the partition problem is NP-complete by reduction to integer subset sum problem. A lot of proofs explicitly pointed out that the partition problem could take non-integer(not as extreme as irrational) input, but I just don't think they really added up. I think my question is more on the theoretical level, so I don't have to care about Turing machines interpreting irrational numbers? $\endgroup$
    – BM Yoon
    Oct 12, 2020 at 15:39
  • $\begingroup$ My concern with the Turing Machines is just that NP is defined as the languages non-deterministic TMs can recognize in polynomial time and well they can't recognize anything irrational. Anyhow, you did you already prove that you can reduced subsetsum to integer and non-integer partitioning ? Thus showing that it is at least NP-hard and could solve any NP-Problem? $\endgroup$
    – plshelp
    Oct 12, 2020 at 15:43
  • $\begingroup$ How do you represent the input? You have to encode it as a bitstring somehow. $\endgroup$
    – Yuval Filmus
    Oct 12, 2020 at 18:23
  • $\begingroup$ If the numbers are irrational and unrelated, you can answer no almost surely. If they are related, please tell us how. $\endgroup$
    – user16034
    Aug 14 at 11:54

1 Answer 1

Reset to default
1
$\begingroup$

This paper, On Strong NP-Completeness of Rational Problems , proves that partition problem is strongly NP-complete when all input numbers are rational numbers.

Improve this answer
$\endgroup$

Your Answer

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

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