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

Un étudiant m'a récemment demandé de vérifier une preuve de dureté NP pour eux. Ils ont effectué une réduction selon:

Je réduit ce problème $P'$ qui est connu pour être NP-complet à mon problème $P$ (avec une réduction poly-temps multiple), donc $P$ est NP-dur.

Ma réponse était essentiellement:

Étant donné que $P$ a des instances avec des valeurs de $\mathbb{R}$ , il est trivialement pas calculable par Turing, vous pouvez donc ignorer la réduction.

Bien que formellement vraie, 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, en ignorant les limites auxquelles nous sommes confrontés dans le traitement du réel Nombres; enquêter sur ces questions est pour un autre jour.

Bien sûr, ce n'est pas toujours aussi facile que de dire: "la version discrète de Subset Sum est NP-complète, donc la version continue est" NP-hard "également". Dans ce cas, la réduction est facile, mais il existe des cas célèbres où la version continue est plus facile, par exemple la programmation linéaire par rapport à la programmation entière.

Il m'est venu à l'esprit que le modèle RAM s'étend naturellement aux nombres réels; laissez chaque registre stocker un nombre réel et étendez 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 modèle logarithmique ne l'est pas.

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

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

Oui. Il y a.

Il y a le modèle réel RAM / BSS mentionné dans l'autre réponse. Le modèle a quelques problèmes et AFAIK il n'y a pas beaucoup d'activités de recherche à ce sujet. On peut dire que ce n'est pas un modèle de calcul réaliste .

La notion la plus active de calculabilité réelle est celle d'un modèle de calcul de type supérieur. L'idée de base est que vous définissez la complexité des fonctions de type supérieur, puis utilisez des fonctions de type supérieur pour représenter les nombres réels.

L'étude de la complexité des fonctions de type supérieur remonte au moins à [1]. Pour les travaux récents, consultez les articles d' Akitoshi Kawamura sur la complexité des opérateurs réels.

La référence classique pour la complexité des fonctions réelles est le livre de Ker-I Ko [2]. Le sixième chapitre, le livre le plus récent de Klause Weihrauch [3], traite également de la complexité de la comptabilité réelle (mais il est plus axé sur la calculabilité que sur la complexité).

• [1] Stephen Cook et Bruce Kapron, "Caractérisations des fonctions de base réalisables de type fini", 1990.

• [2] Ker-I Ko, "Complexité computationnelle des fonctions réelles", 1991.

• [3] "Analyse calculable" de Klaus Weihrauch, 2000.

Le modèle que vous décrivez est connu sous le nom de modèle Blum-Shub-Smale (BSS) (également modèle Real RAM) et est en effet utilisé pour définir les classes de complexité.

Certains problèmes intéressants dans ce domaine sont les classes , N P R , et bien sûr la question de savoir si P R = N P R . Par P R, nous voulons dire que le problème est polynomialement décidable, N P R est que le problème est polynomialement vérifiable. Il y a des questions de dureté / exhaustivité sur la classe N P R . Un exemple d'un problème complet N P R est le problème de Q P S , système polynomial quadratique, où l'entrée est de vrais polynômes dans$P_R$$NP_R$$P_R$$NP_R$$P_R$$NP_R$$NP_R$$NP_R$$QPS$ variables et p 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] de degré au plus 2, et chaque polynôme a au plus 3 variables. La questionsavoir s'il existe une véritable solution courante R n ,telle sorte que p 1 ( a ) , p 2 ( a ) , . . . p n ( a ) = $m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$$p_1(a), p_2(a), ... p_n(a) = 0$. Il s'agit d'un problème complet $NP_R$

Mais plus intéressant, il y a eu des travaux sur la relation entre , (Probalistically Checkable Proofs), sur les réels, c'est-à-dire la classe P C P R , et sur la façon dont elle se rapporte aux modèles de calcul algébrique. Le modèle BSS se déplace sur l'ensemble de N P sur des réels. Ceci est standard dans la littérature, et ce que nous savons aujourd'hui, c'est que N P R a des "preuves longues transparentes" et des "preuves courtes transparentes". Par "épreuves longues transparentes", cela implique: N P R est contenu dans P C P R ( p o l $PCP$$PCP_R$$NP$$NP_R$$NP_R$ . Il y a aussi une extension qui dit que la "version courte (presque) approximative" est également vraie. Peut-on stabiliser la preuve et détecter les défauts en inspectant considérablement moins de composants (réels) que n ? Cela conduit à des questions sur l'existence de zéros pour les (systèmes de) polynômes univariés donnés par le programme en ligne droite. En outre, par "preuves longues transparentes", nous entendons$PCP_R(poly, O(1))$$n$

1. "transparent" - Seulement, à lire,$O(1)$

2. long - nombre superpolynomial de composants réels.

La preuve est liée à , et bien sûr, une façon d'examiner les problèmes à valeur réelle est de savoir comment cela pourrait être lié à la sous-somme - même les algorithmes d'approximation pour les problèmes à valeur réelle seraient intéressants - comme pour l'optimisation - Programmation linéaire que nous connaissons est dans la classe F P , mais oui, il serait intéressant de voir comment l'approximation pourrait influer sur l'exhaustivité / la dureté dans le cas des problèmes N P R. De plus, une autre question serait le N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

En pensant à la classe , il existe également des classes de comptage définies pour permettre de raisonner sur l'arithmétique polynomiale. Alors que # P est la classe de fonctions f définie sur { 0 , 1 } ∞ → N pour laquelle il existe une machine de Turing à temps polynomial M et un polynôme p avec la propriété que ∀ n ∈ N , et x ∈ { 0 , 1 } n , f ( x $NP_R$$\#P$$f$$\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$$M$$p$$\forall n$$\in$$\mathbb{N}$$x$$\in$$\{0,1\}^{n}$$f(x)$compte le nombre de chaînes { 0 , 1 } p ( n ) que la machine de Turing M accepte { x , y } . Pour les réels, nous étendons cette idée, il existe des machines BSS additives - des machines BSS qui ne font que des additions et des multiplications (pas de divisions, pas de soustractions). Avec les machines BSS additives (les nœuds dans le calcul ne permettent que l'addition et la multiplication) le modèle pour # P devient celui dans lequel le comptage est sur les vecteurs que les machines BSS additives acceptent. Donc, la classe de comptage est # P a d $y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ cette classe est utile dans l'étude des nombres de Betti, ainsi que la caractéristique d'Euler.