<p>Depending on which version of $\mathsf{NP}_{\mathbb{R}}$ you use, yes or it's open. When one considers BSS machines that only use addition and subtaction, and only branch on equality, the answer is yes. If one includes branching on $&lt;$, I believe it is still open, and the same if one allows multiplications. For details, see <a href="http://dx.doi.org/10.1016/S0020-0190(97)00060-4" rel="nofollow">Cucker, Koiran, and Matamala "Complexity and dimension," Inform. Proc. Lett. 1997</a></p>

CC BY-SA 3.0
2014-09-26T20:23:58.233Z
Sensitivity to the operations is crucial to the machine, for instance if we only allow for addition, and multiplication for the machine, the sets recognized by the BSS machine change.
user3483902
CC BY-SA 3.0
2014-09-26T20:07:42.730Z
2014-10-07T18:09:06.233Z
2014-10-07T18:09:06.233Z
Joshua Grochow
<p>Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$,   (where a <a href="http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine" rel="nofollow">BSS</a> is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. So, the question is
is there an analog of the Berman Hartmanis conjecture for the class NP$_{\mathbb{R}}$? Of course, the question posed here is dependent on the model - in other words, as the definition of NP$_\mathbb{R}$ uses the BSS model, do all of NP$_{\mathbb{R}}$-complete problems have the same structure using the BSS model(this approximates the Berman-Hartmanis conjecture for NP over reals)?</p>

<cc.complexity-theory><computing-over-reals>
Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?
user3483902
# Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?

(Asked by: username_0 on 2014-09-25)

Using the real-RAM/BSS model, we have the class NP$\_{\mathbb{R}}$, (where a [BSS](http://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine) is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$\_{\mathbb{R}}$ complete problems. So, the question is
is there an analog of the Berman Hartmanis conjecture for the class NP$\_{\mathbb{R}}$? Of course, the question posed here is dependent on the model - in other words, as the definition of NP$\_\mathbb{R}$ uses the BSS model, do all of NP$\_{\mathbb{R}}$-complete problems have the same structure using the BSS model(this approximates the Berman-Hartmanis conjecture for NP over reals)?

**Tags:** cc.complexity-theory, computing-over-reals

---

## 1 answers

### Answer by username_1 on 2014-09-26. Score: 7 | Accepted answer

Depending on which version of $\mathsf{NP}\_{\mathbb{R}}$ you use, yes or it's open. When one considers BSS machines that only use addition and subtaction, and only branch on equality, the answer is yes. If one includes branching on $<$, I believe it is still open, and the same if one allows multiplications. For details, see [Cucker, Koiran, and Matamala "Complexity and dimension," Inform. Proc. Lett. 1997](http://dx.doi.org/10.1016/S0020-0190(97)00060-4)

> **Comments:**
> **username_0**: Sensitivity to the operations is crucial to the machine, for instance if we only allow for addition, and multiplication for the machine, the sets recognized by the BSS machine change.  

---

