6
$\begingroup$

The Partition problem is: given $n$ numbers in the range $[0,M]$, decide if they can be partitioned into two subsets with equal sum.

If the numbers are integers, then the problem is NP-complete, but has a dynamic-programming algorithm that runs in pseudo-polynomial time, polynomial in $M$ and $n$.

Suppose now that the numbers are real, and we have a Real RAM machine, where every real number can be stored in a single memory cell, and every arithmetic operation on real numbers takes a single time unit. What is known about the run-time complexity of the problem?

  1. On one hand, the Real RAM model is stronger than the Turing model, so the NP-hardness of Partition in the Turing model does not immediately imply hardness in the Real RAM model.

  2. On the other hand, the dynamic-programming algorithm does not work, since there are uncountably many possible sums in the range $[0,M]$.

What is the run-time complexity of the Partition problem with real numbers in the Real RAM model? In particular:

  1. Is there a proof that it cannot be solved in polynomia time unless P=NP?

  2. is there a proof that no pseudo-polynomial time algorithm exists?

EDIT: The optimization variant of the Partition problem (finding a partition which maximizes the minimum sum) has an FPTAS, which is based on rounding the dynamic program. So a related question is: does the Partition problem has an FPTAS in the Real RAM model?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ can we check once if the (decision version of) problem lies in RE? I suspect it to lie outside. // Reason: out of any two possible partitions of the [0, M] set, at least one of the subsets must be uncountably infinite in size. Also, such a sum diverges. (Let me know if you find a bug in my argument.) $\endgroup$
    – Manish Kumar
    Commented May 22 at 14:50
  • 3
    $\begingroup$ @108_mk In the Real RAM model we can simply try out all $2^{n-1}$ many partitions, compute the sums and check whether they are equal. $\endgroup$
    – Arno
    Commented May 22 at 21:55
  • $\begingroup$ Are there any problems that are NP-complete in the Real RAM model? $\endgroup$
    – domotorp
    Commented May 28 at 7:40

1 Answer 1

Reset to default
0
$\begingroup$

I did not find an answer, but I found a related paper:

Jeff Erickson, Ivor van der Hoog and Tillmann Miltzow, "Smoothing the gap between NP and ER", in SIAM Journal on Computing 2022 (preliminary version in FOCS 2020).

In Section 5 they write:

we define formally a model of the real RAM. This model corresponds to the model that is intuitively used by researchers in computational geometry for decades. Yet, it is still conceivable that one can design a polynomial time algorithm for SAT on the real RAM, even if P = NP. Yet, this paper gives several arguments that support the intuition that those pitfalls will not happen... assume that we have an algorithm SAT-SOLVE that can determine in polynomial time on a real RAM if a given SAT formula is true, then Theorem 2 implies co-NP $\subseteq \exists R$. In addition, if there were an algorithm that would solve true quantified Boolean formulas (TQBF) in polynomial time on a real RAM, then Theorem 2 would even imply $\exists R = PSPACE$. Still, it seems difficult to rule out a polynomial time algorithm for SAT on the real RAM, as we can also not rule out a SAT algorithm on the word RAM.

I believe the same should be true for Partition. If it is true, then the runtime complexity of Partition on a Real RAM machine is still open. But maybe I misunderstood something.

Improve this answer
$\endgroup$

Your Answer

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

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