Y a-t-il des classes de complexité établies avec des nombres réels?

Question

Un étudiant m'a récemment demandé de vérifier une preuve du NP-Sardness pour eux. Ils ont effectué une réduction dans le sens de:

Je réduit ce problème $ p '$ qui est connu pour être NP-Complete à mon problème $ P $ (avec une réduction en poly de plusieurs fois), donc $ p $ est NP-dur.

Ma réponse était essentiellement:

Puisque $ p $ a des instances avec des valeurs de $ mathbb {r} $, il est trivialement non-calculable afin que vous puissiez ignorer la réduction.

Bien que formellement vrai, je ne pense pas que cette approche soit perspicace: nous aimerions certainement être en mesure de saisir la "complexité inhérente" d'un problème de décision (ou d'optimisation) à valeur réelle, ignorant les limites auxquelles nous sommes confrontés en traitant de réels Nombres; L'enquête sur ces problèmes est pour un autre jour.

Il n'est bien sûr pas toujours aussi simple que de dire: "La version discrète de la somme du sous-ensemble est NP-complete, donc la version continue est également" NP-dur "". Dans ce cas, la réduction est facile, mais il existe des cas célèbres de la version continue étant plus facile, par exemple la programmation linéaire vs entière.

Il m'est venu à l'esprit que le modèle RAM s'étend naturellement à des nombres réels; Laissez chaque enregistrement stocker un nombre réel et étendre les opérations de base en conséquence. Le modèle de coût uniforme a toujours du sens - autant que dans le cas discret, de toute façon - tandis que le logarithmique ne le fait pas.

Donc, ma question se résume à: y a-t-il des notions établies de complexité des problèmes de valeur réelle? Comment sont-ils liés aux classes discrètes "standard"?

^{Les recherches Google donnent des résultats, par exemple cette, mais je n'ai aucun moyen de dire ce qui est établi et / ou utile et ce qui ne l'est pas.}