Questions liées à la dureté NP et à l'exhaustivité NP.
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...
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...
À l' heure actuelle, la résolution soit une problème -complete ou un P S P A C E problème -complete est impossible dans le cas général pour les grandes entrées. Cependant, les deux peuvent être résolus en temps exponentiel et en espace polynomial.NPNPNPPSPUn cEPSPACEPSPACE Puisque nous ne pouvons...
Je cherche des exemples de problèmes paramétrés par un nombre , où la dureté du problème est non monotone en . La plupart des problèmes (selon mon expérience) ont une transition de phase unique, par exemple -SAT a une transition de phase unique de (où le problème est en P) à (où le le problème est...
J'ai rencontré l'algorithme polynomial qui résout 2SAT. J'ai trouvé ahurissant que 2SAT soit dans P où toutes (ou beaucoup d'autres) des instances SAT sont NP-Complete. Qu'est-ce qui rend ce problème différent? Qu'est-ce qui le rend si facile (NL-Complete - encore plus facile que...
Plusieurs problèmes d'optimisation connus pour être NP-difficiles sur les graphes généraux peuvent être résolus de manière triviale en temps polynomial (certains même en temps linéaire) lorsque le graphe en entrée est un arbre. Les exemples incluent la couverture de vertex minimale, le jeu maximum...
Le livre d’ Arora et Barak présente l’affacturage comme le problème suivant: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Ils ajoutent, plus...
Je pense au problème suivant: je veux trouver une expression régulière qui correspond à un ensemble particulier de chaînes (par exemple, des adresses électroniques valides) et ne correspond à aucune autre (adresses électroniques non valides). Supposons que par expression régulière, nous entendons...
Ceci est un post-cross de math.stackexchange. Soit FACT représentent le problème de factorisation d'entiers: étant donné trouver des nombres premiers p i ∈ N , et les entiers e i ∈ N , de telle sorte que n = Π k i = 0 p e i i .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in...
Pourquoi la plupart des gens préfèrent-ils utiliser plusieurs réductions pour définir l'exhaustivité des NP au lieu, par exemple, des réductions de
É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...
Mark Dominus a rassemblé quelques exemples de réduction du temps polynomial de divers problèmes NP-difficiles à la correspondance «d'expression régulière» . Envisager des vérifications en temps polynomial n'est pas un énorme pas en avant. Comment illustrez-vous la classe NP-complete aux étudiants...
J'ai une question historique. J'essaie de déterminer la référence pour le fait que la possibilité de coloration sur 3 des graphes (ou colourability pour un ) est NP-difficile.k ≥ 3kkkk ≥ 3k≥3k\geq 3 La réponse tentante est «le papier original de Karp», mais c'est faux. Voici une analyse:...
Tout nombre naturel peut être considéré comme une séquence de bits, donc la saisie d'un nombre naturel est la même que la saisie d'une séquence 0-1, donc des problèmes NP-complets avec des entrées naturelles existent évidemment. Mais y a-t-il des problèmes naturels, c'est-à-dire ceux qui...
Soit un problème (de décision) dans NP et soit # sa version de comptage.XXXXXX Dans quelles conditions sait-on que "X est NP-complet" "#X est # P-complet"?⟹⟹\implies Bien sûr, l'existence d'une réduction parcimonieuse est une de ces conditions, mais c'est évident et la seule de ces conditions que...
Il y avait deux questions posées récemment sur cs.se qui étaient liées ou avaient un cas spécial équivalent à la question suivante: Supposons que vous ayez une séquence de n nombres tels que ∑ n i = 1 a i = n ( n + 1 ) . Décomposer en la somme de deux permutations, π et σ , de 1 … n , de sorte que...
Est-il judicieux de considérer une catégorie de tous les problèmes NP-complets, avec des morphismes comme des réductions de poly-temps entre différentes instances? Quelqu'un a-t-il déjà publié un article à ce sujet, et si oui, où puis-je le
Nous savons que (voir, par exemple, les théorèmes 1 et 3 de [1]), en gros, dans des conditions appropriées, des fonctions qui peuvent être efficacement calculées par la machine de Turing en temps polynomial ("efficacement calculable") peuvent être exprimées par des réseaux de neurones polynomiaux...
En lisant l'article "Est-il temps de déclarer la victoire en comptant la complexité?" sur le blog "Godel's Lost Letter and P = NP" , ils ont mentionné la dichotomie pour les CSP. Après quelques liens après, googler et wikipeding, je suis tombé sur le théorème de Ladner : Théorème de Ladner: Si ,...
J'ai trouvé ce document très intéressant. Pour résumer: il explique pourquoi, dans la pratique, vous trouvez rarement le pire cas d'un problème NP-complet. L'idée de l'article est que les instances sont généralement très sous ou très contraignantes, les deux étant relativement faciles à résoudre....