Quels sont les problèmes non triviaux où nous savons que l'algorithme actuel que nous avons est asymptotiquement optimal? (Pour les machines de turing) Et comment cela est-il
Il y a eu un travail fantastique sur le permanent en cours au cours des deux dernières décennies et je m'interroge depuis un moment sur la possibilité d'un algorithme Smooth P pour le permanent des matrices non négatives. Il y a bien sûr le fameux algorithme JSV mais c'est un fpras. En pensant à...
Étant donné deux CNF, s'ils ont le même nombre d'affectations pour les rendre vraies, répondez "Oui", sinon répondez "Non". Il est facile de voir que c'est dans , car si nous connaissons le nombre exact de solutions à ces deux CNF, nous les campons simplement et répondons "Oui" ou...
1) Est-il possible d'avoir une réduction parcimonieuse d'un problème # P-complet #A à un problème de comptage #B quand (la version de décision) A est NP-complet et le B est en P? Par exemple, peut-il y avoir une réduction parcimonieuse de #SAT à #B, lorsque B est dans P? 2) Si B est dans P, quelles...
J'avais fait quelques recherches à ce sujet mais je n'ai pas pu trouver de réponse dans les deux cas. Huck y répondit pleinement. Merci
Je sais que (nombre d'appels logarithmiques à l'oracle NP) est équivalent à (polynôme nombre de requêtes parallèles à l’oracle NP). Je me demandais si la version "fonctionnelle" de ces classes était également équivalente, c'est-à-dire siP N P | |PN P [logn
Existe-t-il des problèmes intéressants dans mais non connus dans ? Dans l'article «Une taxonomie des problèmes avec les algorithmes parallèles rapides», Cook mentionne que MIS était connu pour être uniquement dans mais cela a depuis été ramené à . Je me demande s'il y a d'autres problèmes avec les...
Pendant longtemps, j'ai pensé qu'un problème était NP-complet s'il était à la fois (1) NP-dur et (2) en NP. Cependant, dans le célèbre article "La méthode ellipsoïde et ses conséquences dans l'optimisation combinatoire" , les auteurs affirment que le problème du nombre chromatique fractionnaire...
Cette question a été posée par Jan Pax sur la liste de diffusion Foundations of Mathematics . Certainement mais je soupçonne d'après les réponses à cette question que l'on ne sait pas si ⊕ P ⊆ P P (sinon, P P serait une réponse possible à cette question). Si ce n'est pas connu, y a-t-il une...
Je lis l'annexe sur les limites inférieures de l'ACC pour NEXP dans le livre Arora et Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf L'un des lemmes clés est une transformation des circuits ACC0ACC0ACC^{0} en polynômes multilinéaires sur les...
La classe de complexité PPAD est généralement définie en indiquant que End-Of-The-Line est PPAD-complete. La fin de ligne est un problème de recherche. L'entrée consiste en un graphe orienté dans lequel chaque nœud a au plus en degré et en degré 1. Le graphe est donné par une fonction calculable en...
De nombreuses classes de complexité définies avec les machines de Turing ont des définitions en termes de circuits uniformes. Par exemple, P peut également être défini en utilisant des circuits de taille polynomiale uniforme, et de même BPP, NP, BQP, etc. peuvent être définis avec des circuits...
Une question récente (voir les conséquences de NP = PSPACE ) a demandé des conséquences "désagréables" de . Les réponses liste assez peu de conséquences de l' effondrement, y compris N P = c o N P et d' autres, en fournissant beaucoup de raisons de croire N P ≠ P S P A C E...
Chaque fois que j'enseigne la NP-Complétude, les étudiants demandent "y a-t-il des problèmes connus pour ne pas appartenir à NP?" Comment répondriez-vous? Je leur donne généralement un problème indécidable à titre d'exemple, mais cela ne tourne souvent pas bien: (a) si je leur donne le problème de...
Le théorème de prétention parallèle de Raz est un résultat important dans le PCP, l'inapproximation, etc. Le théorème est fomalisé comme suit. Un jeu , où S , T , A , B sont des ensembles finis, π est une distribution sur S × T et un prédicat V : S × T × A × B → { 0 , 1 } . Définir la valeur du jeu...
P / poly est la classe de problèmes de décision pouvant être résolus par une famille de circuits booléens de taille polynomiale. Il peut également être défini comme une machine de Turing à temps polynomial qui reçoit une chaîne de conseils de taille polynomiale en n et basée uniquement sur la...
Les éléments suivants peuvent-ils tous tenir simultanément? LsLsL_s est contenu dansLs+1Ls+1L_{s+1} pour tous les entiers positifssss . { 0 , 1 }L=⋃sLsL=⋃sLsL = \bigcup_s L_s est la langue de tous les mots finis sur .{0,1}{0,1}\{0,1\} Il y a une classe de complexité et une notion de réduction...
Considérons le jeu suivant sur un graphique pondéré dirigé avec une puce à un nœud.GGG Tous les nœuds de sont marqués par A ou B.GGG Il y a deux joueurs Alice et Bob. Le but d'Alice (Bob) est de déplacer la puce vers un nœud marqué par A (B). Initialement, Alice et Bob ont respectivement et...
Quels sont les autres langages de problèmes différents de l'isomorphisme des graphes dans ? Pouvez-vous donner quelques références?NP∩ c o A MNP∩coAMNP\cap coAM Mise à jour: J'ai oublié de mentionner que je suis intéressé dans les langues ne sont pas connus pour être en .c o...
Par http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Si est un langage complet-PSPACE, P A = N P A .UNEAAPUNE= NPUNEPA=NPAP^{A}=NP^{A} Si est un oracle à temps polynomial déterministe, P B ≠ N P B (en supposant P ≠ N P ).BBBPB≠ NPBPB≠NPBP^{B}\ne NP^{B}P≠ NPP≠NPP\ne NP est la classe de...