Isomorfismo de Berman-Hartmanis para NP ?

Usando el modelo real-RAM / BSS, tenemos la clase NP , (donde un BSS es el modelo Blum-Shub-Smale de una computadora con operaciones sobre reales). Tenemos problemas completos de NP . Entonces, la pregunta es ¿hay un análogo de la conjetura de Berman Hartmanis para la clase NP ? Por supuesto, la pregunta que se plantea aquí depende del modelo; en otras palabras, como la definición de NP usa el modelo BSS, ¿todos los problemas completos de NP tienen el misma estructura usando el modelo BSS (esto se aproxima a la conjetura de Berman-Hartmanis para NP sobre reales)?$_{\mathbb{R}}$$_{\mathbb{R}}$$_{\mathbb{R}}$$_\mathbb{R}$$_{\mathbb{R}}$

Dependiendo de la versión de que use, sí o está abierto. Cuando uno considera máquinas BSS que solo usan suma y subtacción, y solo se ramifican en igualdad, la respuesta es sí. Si se incluye la ramificación en , creo que todavía está abierto, y lo mismo si se permite la multiplicación. Para más detalles, vea Cucker, Koiran y Matamala "Complejidad y dimensión", Informe. Proc. Letón. 1997$\mathsf{NP}_{\mathbb{R}}$$<$