<p>I did not find an answer, but I found a related paper:</p>
<blockquote>
<p>Jeff Erickson, Ivor van der Hoog and Tillmann Miltzow, &quot;<a href="https://epubs.siam.org/doi/abs/10.1137/20M1385287" rel="nofollow noreferrer">Smoothing the gap between NP and ER</a>&quot;, in SIAM Journal on Computing 2022 (preliminary version in FOCS 2020).</p>
</blockquote>
<p>In Section 5 they write:</p>
<blockquote>
<p>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 <span class="math-container">$\subseteq \exists R$</span>.
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 <span class="math-container">$\exists R = PSPACE$</span>.
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.</p>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2024-05-28T08:02:39.857Z
2024-05-28T08:02:39.857Z
Erel Segal-Halevi
<p>The Partition problem is: given <span class="math-container">$n$</span> numbers in the range <span class="math-container">$[0,M]$</span>, decide if they can be partitioned into two subsets with equal sum.</p>
<p>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 <span class="math-container">$M$</span> and <span class="math-container">$n$</span>.</p>
<p>Suppose now that the numbers are real, and we have a <a href="https://en.wikipedia.org/wiki/Real_RAM" rel="nofollow noreferrer">Real RAM</a> 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?</p>
<ol>
<li><p>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.</p>
</li>
<li><p>On the other hand, the dynamic-programming algorithm does not work, since there are uncountably many possible sums in the range <span class="math-container">$[0,M]$</span>.</p>
</li>
</ol>
<p>What is the run-time complexity of the Partition problem with real numbers in the Real RAM model? In particular:</p>
<ol>
<li><p>Is there a proof that it cannot be solved in polynomia time unless P=NP?</p>
</li>
<li><p>is there a proof that no pseudo-polynomial time algorithm exists?</p>
</li>
</ol>
<p>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?</p>

CC BY-SA 4.0
2024-05-22T14:50:57.703Z
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.)
Manish Kumar
CC BY-SA 4.0
2024-05-22T21:55:52.730Z
@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.
Arno
CC BY-SA 4.0
2024-05-28T07:40:28.090Z
Are there any problems that are NP-complete in the Real RAM model?
domotorp
<partition-problem><computing-over-reals>
Complexity of the Partition problem in the Real RAM model
Erel Segal-Halevi
# Complexity of the Partition problem in the Real RAM model

(Asked by: username_0 on 2024-05-20)

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](https://en.wikipedia.org/wiki/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?

**Tags:** partition-problem, computing-over-reals
> **Comments:**
> **username_1**: 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.)  
> **username_2**: @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.  
> **username_3**: Are there any problems that are NP-complete in the Real RAM model?  

---

## 1 answers

### Answer by username_0 on 2024-05-28. Score: 1

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](https://epubs.siam.org/doi/abs/10.1137/20M1385287)", 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.


---

