Conséquences de #P = FP

Quelles seraient les conséquences de #P = FP?

Je m'intéresse aux conséquences pratiques et théoriques.

D'un point de vue pratique, je m'intéresse particulièrement aux conséquences sur l'intelligence artificielle.

Les pointeurs vers des articles ou des livres sont plus que bienvenus.

Veuillez ne pas dire que #P = FP implique P = NP, je le sais déjà. Aussi, veuillez ne pas dire "il n'y aura pas de conséquences pratiques si l'algorithme fonctionne dans le temps , où est le nombre d'électrons dans l'Univers" $\Omega(n^{\alpha})$ $\alpha$ : permettez-moi de supposer que, si un algorithme de temps polynomial déterministe pour un problème # P-complete existe, son temps d'exécution sera "clement" ( , par exemple). $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
la source

Réponses:

Voici quelques conséquences théoriques de l'égalité FP = # P, bien qu'elles n'aient rien à voir avec l'intelligence artificielle. L'hypothèse FP = # P est équivalente à P = PP , alors permettez-moi d'utiliser la dernière notation.

Si P = PP, alors nous avons P = BQP : le calcul quantique du temps polynomial peut être simulé par un calcul classique, déterministe du temps polynomial. Ceci est une conséquence directe de BQP⊆PP [ADH97, FR98] (et d'un résultat antérieur BQP⊆P ^PP [BV97]). En plus de mes connaissances, P = BQP n'est pas connu pour découler de l'hypothèse P = NP. Cette situation est différente du cas du calcul aléatoire ( BPP ): depuis BPP⊆NP ^NP [Lau83], l'égalité P = BPP découle de P = NP.

Une autre conséquence de P = PP est que le modèle de calcul Blum-Shub-Smale sur les réels à constantes rationnelles est équivalent aux machines de Turing dans un certain sens. Plus précisément, P = PP implique P = BP (P _ℝ⁰ ); c'est-à-dire que si un langage L ⊆ {0,1} ^* est décidable par un programme sans constante sur les réels en temps polynomial, alors L est décidable par une machine de Turing en temps polynomial. (Ici, «BP» signifie «partie booléenne» et n'a rien à voir avec BPP.) Cela découle de BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. Voir le document pour les définitions. Un problème important dans BP (P _ℝ⁰ ) est le problème de la somme des racines carrées et amis (par exemple «Étant donné un entier ket un ensemble fini de points de coordonnées entières sur le plan, y a-t-il un arbre couvrant de longueur totale au plus k ?») [Tiw92].

Comme pour le deuxième argument, le problème du calcul d'un bit spécifique dans x ^y lorsque des entiers positifs x et y sont donnés en binaire sera dans P si P = PP.

Les références

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen et Peter Bro Miltersen. Sur la complexité de l'analyse numérique. SIAM Journal on Computing , 38 (5): 1987-2006, janvier 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais et Ming-Deh A. Huang. Calculabilité quantique. SIAM Journal on Computing , 26 (5): 1524-1540, octobre 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein et Umesh Vazirani. Théorie de la complexité quantique. SIAM Journal on Computing , 26 (5): 1411–1473, octobre 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow et John Rogers. Limitations de complexité sur le calcul quantique. Journal of Computer and System Sciences , 59 (2): 240–252, octobre 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP et la hiérarchie polynomiale temporelle. Lettres de traitement de l'information , 17 (4): 215-217, novembre 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Un problème plus facile à résoudre sur la RAM algébrique à coût unitaire. Journal of Complexity , 8 (4): 393–397, décembre 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
la source

Tu m'as battu à ça! En fait, vous avez raison sur BQP vs NP. Il semble y avoir des preuves raisonnables que BQP n'est pas contenu dans PH (voir par exemple arxiv.org/abs/0910.4698 ), bien que je pense que la conjecture généralisée Linial-Nisan qui est utilisée dans le deuxième bit s'est depuis avérée incorrecte.

Joe Fitzsimons

@turkistany: Si je ne me trompe pas, P = NP implique P = BPP car BPP est contenu dans PH, et si P = NP alors P = PH.

Niel de Beaudrap

Incidemment: +1 pour (FP = # P) ⇔ (P = PP), même en mettant de côté le reste du contenu de la réponse.

Niel de Beaudrap

@Joe: À la lumière des réponses à l'autre question, je pense que la meilleure preuve de «P = NP n'implique pas P = BQP» sans prouver réellement P = NP ≠ BQP serait probablement un résultat de séparation d'oracle: «Il existe un oracle A tel que P ^ A = NP ^ A ≠ BQP ^ A. ”Bien sûr, ce n'est pas facile du tout parce que ce résultat impliquerait BQP ^ A⊈PH ^ A, réglant une grande question ouverte.

Tsuyoshi Ito du

@Tsuyoshi: Ne pouvez-vous pas construire un tel oracle à partir d'un oracle par rapport auquel BQP n'est pas contenu dans PH, simplement en le combinant avec PH pour former un nouvel oracle?

Joe Fitzsimons

Dans les modèles graphiques , de nombreux problèmes d'estimation sont # P-complets, car ils impliquent de faire des calculs de somme de produits à la manière des graphiques permanents par rapport aux graphiques généraux. Si #P = FP, alors les modèles graphiques deviennent soudainement beaucoup plus faciles, et nous n'avons plus besoin de fouiner avec des modèles à faible largeur d'arbre.

Suresh Venkat
la source

$PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Mohammad Al-Turkistany
la source

Quelqu'un peut-il préciser: n'est-ce pas la même chose que de dire "P = PH" (qui découlerait immédiatement de P = NP)?

Niel de Beaudrap

@Niel: Ce n'est pas pareil, c'est plus fort.

Giorgio Camerani,

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

@All: juste pour clarifier --- mon premier commentaire ci-dessus posait la question suivante "La réponse de la Turquie est-elle équivalente à l'affirmation selon laquelle FP = # P implique P = PH?" Si je voulais savoir si FP = # P était équivalent à P = PH, je l'aurais demandé dans un commentaire sur le message original, pas sur la réponse de turkistany.

Niel de Beaudrap du

@Niel: Tu as raison. Cela revient à dire P = PH, qui découle de P = NP. Par conséquent, l'utilisation du théorème de Toda n'était pas nécessaire, car FP = #P implique déjà P = NP = PH.

Robin Kothari