La factorisation et l'isomorphisme des graphes sont des problèmes dans NP qui ne sont connus ni pour P ni pour NP-Complete. Quels autres problèmes naturels (suffisamment différents) partagent cette propriété? Les exemples artificiels directement issus de la démonstration du théorème de Ladner ne...
Le théorème de Ladner stipule que si P ≠ NP, il existe une infinie hiérarchie de classes de complexité contenant strictement P et strictement contenu dans NP. La preuve utilise l'intégralité de la SAT sous plusieurs réductions de NP. La hiérarchie contient des classes de complexité construites...
Étant donné un nouveau problème dans dont la véritable complexité se situe quelque part entre et NP-complete, il existe deux méthodes que je connais qui pourraient être utilisées pour prouver que la résolution de ce problème est difficile:NPNP\mathsf{NP}PP\mathsf{P} Montrer que le problème est...
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...
Il est bien connu par le théorème de Ladner que si , alors il existe une infinité de problèmes -intermediate ( ). Il existe également des candidats naturels pour ce statut, tels que l'isomorphisme graphique, et un certain nombre d'autres, voir Problèmes entre P et NPC . Néanmoins, la grande...
Peter Shor a montré que deux des problèmes NP-intermédiaires les plus importants, l'affacturage et le problème de log discret, sont en BQP. En revanche, le meilleur algorithme quantique connu pour SAT (recherche de Grover) ne produit qu'une amélioration quadratique par rapport à l'algorithme...
László Babai a récemment prouvé que le problème d'isomorphisme des graphes est en temps quasi-polynomial . Voir également son exposé à l'Université de Chicago, note des exposés de Jeremy Kun GLL post 1 , GLL post 2 , GLL post 3 . Selon le théorème de Ladner, si P≠NPP≠NPP \neq NP , alors NPINPINPI...
Supposons que . N P I est la classe de problèmes en N P qui ne sont ni en P ni en N P -hard. Vous pouvez trouver une liste des problèmes supposés être N P I ici .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPje\mathsf{NPI}NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} Le théorème de Ladner...
L'isomorphisme graphique ( ) est un bon candidat pour un problème intermédiaire . problèmes intermédiaires existent sauf si . Je recherche un problème naturel difficile pour sous réduction de Karp (Un problème graphique tel que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
Supposons P NP.≠≠\ne Le théorème de Ladner dit qu'il existe des problèmes NP intermédiaires (problèmes dans NP qui ne sont ni dans P ni NP-Complete). J'ai trouvé en ligne des références voilées qui suggèrent (je pense) qu'il existe de nombreux "niveaux" de langues mutuellement réductibles au sein...
J'essaie de comprendre à quelle classe de complexité appartient le problème suivant: Exponentiating Polynomial Root Problem (EPRP) Soit un polynôme avec deg ( p ) ≥ 0 avec des coefficients tirés d'un champ fini G F ( q ) avec q un nombre premier, et r une racine primitive pour ce champ. Déterminez...
Pouvons-nous prouver que pour chaque langue qui n'est pas -hard (cela suppose ), ? Sinon, cela peut-il être prouvé sous des hypothèses raisonnables?L∈NPL∈NPL\in\mathsf{NP}NPNP\mathsf{NP}P≠NPP≠NP\mathsf P \ne \mathsf{NP}PL≠PSATPL≠PSAT\mathsf{P}^L \ne
Comment peut-on considérer un problème et pourquoi il est probable NP-intermédiaire par opposition à NP-complet? Il est souvent assez simple d'examiner un problème et de dire s'il est probablement NP-complet ou non, mais il me semble beaucoup plus difficile de dire si un problème est...
Il existe certains problèmes NP-Complete ( , S U B S E T S U M , etc.) connus pour être dans D S P A C E ( n ) . Et les espaces sub-linéaires?SATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Existe-t-il un problème NP-complet (ou NP-intermédiaire)...