Classes de complexité informatique et leurs relations
Norbert Blum a récemment publié une preuve de 38 pages attestant que . Est-ce correct?P≠ NPP≠NPP \ne NP Également sur le sujet: où d'autre (sur Internet) discute-t-on de son exactitude? Remarque: l'objet de cette question a évolué au fil du temps. Voir les commentaires de la question pour plus de...
Cette question est quelque chose que je me pose depuis un moment. Lorsque les gens décrivent le problème P vs NP, ils comparent souvent la classe NP à la créativité. Ils notent que la composition d'une symphonie de qualité Mozart (analogue à une tâche NP) semble beaucoup plus difficile que de...
Dans la complexité descriptive , Immerman a Corollaire 7.23. Les conditions suivantes sont équivalentes: 1. P = NP. 2. Structures sur finies et ordonnées, FO (LFP) = SO. Cela peut être considéré comme "amplifiant" P = NP en une déclaration équivalente sur (probablement) des classes de complexité...
On sait que L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} et L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , où L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Nous savons aussi que...
Autant que je sache, le programme de théorie de la complexité géométrique tente de séparer en prouvant que le permament d'une matrice à valeurs complexes est beaucoup plus difficile à calculer que le déterminant.VP≠VNPVP≠VNPVP \neq VNP Après avoir parcouru les documents du GCT, la question que je...
La classe de complexité comprend les problèmes de qui peuvent être résolus par une machine de Turing polynomiale non déterministe qui en a au plus un qui accepte le chemin de calcul. C'est-à-dire que la solution, s'il y en a une, est unique en ce sens. Il est hautement improbable que tous les...
La complexité croissante des programmes informatiques et la position de plus en plus cruciale des ordinateurs dans notre société me laissent nous demander pourquoi nous n'utilisons toujours pas collectivement des langages de programmation dans lesquels vous devez prouver formellement que votre code...
Dans l'introduction et l'explication, les classes de complexité P et NP souvent données par la machine de Turing. L'un des modèles de calcul est le lambda-calcul. Je comprends que tous les modèles de calcul sont équivalents (et si nous pouvons introduire n'importe quoi en termes de machine de...
Papadimitriou écrit dans son livre "Computational Complexity": RP est en quelque sorte un nouveau type de classe de complexité inhabituel. Nulle machine de Turing non déterministe à bornes polynomiales ne peut être à la base de la définition d’un langage dans RP. Pour qu'une machine N définisse une...
Du point de vue du sens commun, il est facile de croire que l’ajout du non-déterminisme à PP\mathsf{P} étend considérablement son pouvoir, c’est-à-dire que NPNP\mathsf{NP} est beaucoup plus grand que PP\mathsf{P} . Après tout, le non-déterminisme permet un parallélisme exponentiel, qui apparaît...
En tant qu'amateur de TCS, je lis du matériel très introductif sur l'informatique quantique. Voici les quelques informations élémentaires que j'ai apprises jusqu'à présent: Les ordinateurs quantiques ne sont pas connus pour résoudre des problèmes NP-complets en temps polynomial. "La magie quantique...
Considérez le problème de comptage suivant (ou le problème de décision associé): Étant donné deux entiers positifs codés en binaire, calculez leur plus grand commun diviseur (gcd). Quelle est la plus petite classe de complexité dans laquelle ce problème est contenu? Pouvez-vous fournir une...
Le problème central de la théorie de la complexité est sans doute vs N P .PPPNPNPNP Cependant, comme la nature est quantique, il semblerait plus naturel de considérer les classes (c'est-à-dire les problèmes de décision pouvant être résolus par un ordinateur quantique en temps polynomial, avec une...
Cette question concerne les problèmes pour lesquels il existe un grand écart de complexité ouvert entre la borne inférieure connue et la borne supérieure, mais pas en raison de problèmes ouverts sur les classes de complexité elles-mêmes. Pour être plus précis, disons qu'un problème a des classes...
Dans l'article The Random Oracle Hypothesis Is False , les auteurs (Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan et Rohatgi) discutent des implications de l' hypothèse de l'oracle aléatoire . Ils soutiennent que nous savons très peu de choses sur les séparations entre les classes de...
Il y a une justification philosophique souvent citée pour croire que P! = NP même sans preuve. D'autres classes de complexité ont la preuve qu'elles sont distinctes, car sinon, il y aurait des conséquences "surprenantes" (comme l'effondrement de la hiérarchie polynomiale). Ma question est, quelle...
Il y a des tonnes de problèmes NP-complets et des sources qui les collectent, par exemple, voir le livre de Garey et Johnson. Je serais également intéressé de voir une liste des problèmes NEXP-complete. Y en a-t-il un disponible? Comme je suppose qu'il n'y en a pas, j'ouvre cette question (est-ce...
Quelles seraient les conséquences désagréables de NP = PSPACE? Je suis surpris de n'avoir rien trouvé à ce sujet, étant donné que ces cours sont parmi les plus célèbres. En particulier, cela aurait-il des conséquences sur les classes
On que car l'inverse impliquerait . Le théorème de Ladner établit que si alors . Cependant, la preuve ne semble pas généraliser à donc la possibilité ie semble ouvert.NP⊈P/polyNP⊈P/poly\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}PH=Σ2PH=Σ2\mathsf{PH} = \Sigma_2P≠NPP≠NP\mathsf{P} \ne...
Supposons que P = NP soit vrai. Y aurait-il alors une application pratique à la construction d'un ordinateur quantique, telle que la résolution plus rapide de certains problèmes, ou une telle amélioration serait-elle sans pertinence étant donné que P = NP est vrai? Comment caractériseriez-vous...