Est-il prouvé que le calcul quantique ne résout pas mieux les problèmes complets de NP que le calcul classique ou on le croit
Si est en fait égal à , comment cela améliorerait-il nos algorithmes pour factoriser les entiers plus rapidement. En d'autres termes, quel genre d'information cela nous donnerait-il pour mieux comprendre la factorisation des nombres entiers?PP{\sf P}NPNP{\sf
Planar 3SAT est NP-complet. Une instance planaire 3SAT est une instance 3SAT pour laquelle le graphique construit à l'aide des règles suivantes est planaire: ajouter un sommet pour chaque et ¯ x iXjeXjex_iXje¯Xje¯\bar{x_i} ajouter un sommet pour chaque clauseCjCjC_j ajouter un bord pour chaque...
Je me demande quel est l'algorithme le plus connu, en termes de notation Big- OOO , pour résoudre la programmation linéaire en nombres entiers? Je sais que le problème est NPNPNP complet, donc je ne m'attends à rien de polynomial. Et je sais qu'il y a beaucoup d'heuristiques et autres qui sont...
Le problème 3-Partition demande si un ensemble de entiers peut être partitionné en ensembles de trois nombres entiers tels que chacun des montants mis en place pour un certain nombre entier donné . Le problème de partition équilibrée demande si entiers peuvent être partitionnés en deux ensembles de...
Supposons qu'il y ait une session de tutorat dans une université. Nous avons un ensemble de kkk questions Q={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k \} et un ensemble de nnn élèves S={s1…sn}S={s1…sn}S = \{ s_1 \ldots s_n \} . Chaque élève a un doute dans un certain sous-ensemble de questions,...
Mon conférencier a fait la déclaration Tout problème fini ne peut pas être NP-Complete Il parlait de Sudoku à l'époque en disant quelque chose dans le sens que pour un Sudoku 8x8, il existe un ensemble fini de solutions, mais je ne me souviens pas exactement de ce qu'il a dit. J'ai écrit la note...
Le problème SAT bien connu est défini ici à titre de référence. Le problème DOUBLE-SAT est défini comme DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}DOUBLE-SAT={⟨ϕ⟩∣ϕ has at least two satisfying assignments}\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has...
Donc, je sais que tester si un langage régulier RRR est un sous-ensemble du langage régulier SSS est décidable, car nous pouvons les convertir tous les deux en DFA, calculer R∩S¯R∩S¯R \cap \bar{S} , puis tester si ce langage est vide. Cependant, comme cela nécessite une conversion en DFA, il est...
En termes d'exécution asymptotique dans le pire des cas, quel problème NP-complet a l'algorithme le plus rapide connu (exact) et quel est l'algorithme? Existe-t-il quelque chose de plus rapide que ?O ( n2∗
C'est probablement une question stupide, mais je ne comprends tout simplement pas. Dans une autre question, ils ont proposé le théorème de dichotomie de Schaefer . Pour moi, il semble que cela prouve que chaque problème CSP est soit en P soit en NP-complet, mais pas entre les deux. Étant donné que...
En supposant que nous avons un problème et nous avons montré que la borne inférieure pour résoudre est .ppppppΩ ( 2n)Ω(2n)\mathcal{\Omega}(2^n) la borne inférieure impliquer le problème dans ?Ω ( 2n)Ω(2n)\mathcal{\Omega}(2^n)NPNPNP
J'essaie de résoudre ce problème et j'ai vraiment du mal. Une formule booléenne monotone est une formule en logique propositionnelle où tous les littéraux sont positifs. Par exemple, (x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)(x1∨x2)∧(x1∨x3)∧(x3∨x4∨x5)\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4...
J'ai lu sur NPC et sa relation avec PSPACE et je souhaite savoir si les problèmes NPC peuvent être résolus de manière déterministe en utilisant un algorithme avec un espace polynomial dans le pire des cas, mais prenant potentiellement un temps exponentiel (2 ^ P (n) où P est polynomial). De plus,...
La difficulté d'un problème fortement NP-dur ou NP-complet (tel que défini ici par exemple ) change-t-elle lorsque son entrée est unaire au lieu d'être codée en binaire? Quelle différence cela fait-il si l'entrée d'un problème fortement NP-dur est codée unaire? Je veux dire, si je prends par...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
Le problème suivant est-il NP-complet? (Je suppose que oui). Entrée: un graphique non orienté où l'ensemble de bords peut être décomposé en deux cycles simples à bords séparés (ceux-ci ne font pas partie de l'entrée).k∈N,G=(V,E)k∈N,g=(V,E)k \in \mathbb{N},G=(V,E) Question: Existe - t-il un cycle...
Existe-t-il des algorithmes connus qui donnent correctement "oui" à un problème NP-complet sans générer implicitement un certificat? Je comprends qu'il est simple de transformer un oracle de satisfiabilité en un chercheur d'affectation satisfaisante: il suffit d'itérer sur les variables, en...
Je sais que l'ensemble indépendant maximum sur les graphiques sans triangle cubique est NP-complet. Est-il toujours NP-complet au cas où nous aurions besoin que l'ensemble indépendant soit exactement de la taille ?| V| / 2|V|/2|V|/2 Fondamentalement, l'instance OUI d'un problème d'ensemble...
Je me demande s'il existe un algorithme polynomial pour "2-SAT avec relations XOR". Les deux 2-SAT et XOR-SAT sont en P, mais est-ce que sa combinaison? Exemple d'entrée: Partie 2-SAT: (a or !b) and (b or c) and (b or d) Partie XOR: (a xor b xor c xor 1) and (b xor c xor d) En d'autres termes,...