Isomorphisme de Berman-Hartmanis pour NP ?

En utilisant le modèle réel RAM / BSS, nous avons la classe NP , (où un BSS est le modèle Blum-Shub-Smale d'un ordinateur avec des opérations sur des réels). Nous avons des problèmes complets de NP _ {\ mathbb {R}} . Donc, la question est de savoir s'il existe un analogue de la conjecture de Berman Hartmanis pour la classe NP _ {\ mathbb {R}} ? Bien sûr, la question posée ici dépend du modèle - en d'autres termes, comme la définition de NP _ \ mathbb {R} utilise le modèle BSS, tous les problèmes complets de NP _ {\ mathbb {R}} ont même structure en utilisant le modèle BSS (cela se rapproche de la conjecture de Berman-Hartmanis pour NP sur les réels)?$_{\mathbb{R}}$$_{\mathbb{R}}$$_{\mathbb{R}}$$_\mathbb{R}$$_{\mathbb{R}}$

Selon la version de vous utilisez, oui ou elle est ouverte. Quand on considère les machines BSS qui n'utilisent que l'addition et la sous-action, et ne branchent que sur l'égalité, la réponse est oui. Si l'on inclut la ramification sur , je pense qu'elle est toujours ouverte, et la même chose si l'on autorise les multiplications. Pour plus de détails, voir Cucker, Koiran et Matamala "Complexité et dimension", Informer. Proc. Lett. 1997$\mathsf{NP}_{\mathbb{R}}$$<$