Isomorphisme de Berman-Hartmanis pour NP ?

10

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)?RRRRR

user3483902
la source

Réponses:

8

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. 1997NPR<

Joshua Grochow
la source
1
La sensibilité aux opérations est cruciale pour la machine, par exemple si nous ne permettons que l'addition et la multiplication pour la machine, les ensembles reconnus par la machine BSS changent.
user3483902