Questions marquées «p-hardness»

128
Problèmes entre P et NPC

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...

66
Les problèmes complets

À 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...

47
NP-problèmes difficiles sur les arbres

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...

45
Une variante NP-complète de l'affacturage.

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...

39
Le problème de la factorisation des nombres entiers est-il plus difficile que celui de la factorisation RSA:

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...

34
Rencontres quotidiennes avec des problèmes NP-complets

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...

33
Référence pour la dureté NP de 3 couleurs?

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:...