Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$, (where a BSS 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)?


1 Answer 1


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

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 26, 2014 at 20:23

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.