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...
Considérons le problème suivant dont l'instance d'entrée est un simple graphe et un entier naturel .GGGkkk Existe-t-il un ensemble tel que est biparti et ?S⊆V(G)S⊆V(G)S \subseteq V(G)G−SG−SG - S|S|≤k|S|≤k|S| \leq k Je voudrais montrer que ce problème est -complet en y réduisant 3-SAT, -CLIQUE,...
Je prends un cours sur la complexité informatique. Mon problème est que je ne comprends pas la méthode de relativisation . J'ai essayé de trouver un peu d'intuition dans de nombreux manuels, malheureusement, jusqu'à présent sans succès. J'apprécierai que quelqu'un puisse faire la lumière sur ce...
Considérez l'énoncé du problème suivant: Étant donné un nombre initial, vous et votre ami, à tour de rôle, en soustrayez un carré parfait. Le premier à arriver à zéro gagne. Par exemple: État initial: 37 Le joueur 1 soustrait 16. État: 21 Le joueur 2 soustrait 8. État: 13 Le joueur 1 soustrait 4....
J'ai un problème dans mon esprit, je pense que c'est un problème de PNJ mais je ne sais pas comment le prouver. Voici le problème: Il y a k îles dans un lac très grand, et il y a n pontons en forme d' éventail. Ces pontons sont de la même taille mais ont des directions initiales différentes et sont...
En fait, j'ai trouvé que l'ensemble des langues contextuelles, CSLCSL\mathbf{CSL} ( =NSPACE(O(n))=LBA=NSPACE(O(n))=LBA\mathbf{=NSPACE(O(n)) = LBA} langues acceptées) ne sont pas aussi largement discutées que REGREG\mathbf{REG} (langues régulières) ou CFLCFL\mathbf{CFL} (langues sans contexte). Et...
Formulation alternative Je suis venu avec une formulation alternative au problème ci-dessous. La formulation alternative est en fait un cas particulier du problème ci-dessous et utilise des graphiques bipartites pour décrire le problème. Cependant, je crois que la formulation alternative est...
Mon livre dit ceci Si un problème de décision B est dans P et A se réduit à B, alors le problème de décision A est dans P. Un problème de décision B est NP-complet si B est dans NP et pour chaque problème dans A dans NP, A se réduit à B. Un problème de décision C est NP-complet si C est dans NP et...
Étant donné nombres A 1 ≤ A 2 ≤ . . . ≤ A k tel que k Σ i = 1 A i = k ( 2 k + 1 ) est - il une attribution de numéros i 1 , i 2 , . . . , I 2 k qui est une permutation de 1 , 2 , . . . , 2kkkUNE1≤ A2≤ . . . ≤ AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq A_k∑i = 1kUNEje= k ( 2 k + 1...
Il y a un jeu de livre de puzzle classique très similaire à un puzzle de mots croisés, sauf qu'une liste de mots est donnée, puis un tableau carré composé de carrés d'unité est donné, avec quelques carrés noircis comme un mot croisé, et certains carrés contiennent déjà une lettre pré-écrite. Le but...
Le galet est un jeu de solitaire joué sur un graphe non orienté , où chaque sommet a zéro ou plusieurs galets. Un mouvement de caillou unique consiste à retirer deux cailloux d'un sommet v et à ajouter un caillou à un voisin arbitraire de v . (Évidemment, le sommet v doit avoir au moins deux...
Nous avons eu plusieurs questions sur la relation entre les réductions Cook et Karp . Il est clair que les réductions de Cook (réductions de Turing à temps polynomial) ne définissent pas la même notion de complétude NP que les réductions de Karp (réductions de plusieurs à un temps polynomial), qui...
Étant donné un programme entier (binaire) de la forme:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Notez que la taille de...
Disons que nous savons que le problème A est difficile, puis nous réduisons A au problème inconnu B pour prouver que B est également difficile. Par exemple: nous savons que la coloration 3 est difficile. Ensuite, nous réduisons la coloration 3 à la coloration 4. En combinant l'une des couleurs de...
J'ai un problème que je soupçonne être NP-complet. Il est facile de prouver qu'il s'agit de NP. Mon courant de pensée tourne autour de l'utilisation d'une réduction par rapport au sac à dos, mais il en résulterait des instances de 0-1-sac à dos avec la valeur de chaque élément étant égale à son...
Disons FFF est un oracle pour un problème NPNP\mathbb{NP}, mais je ne peux pas appeler cet oracle avec une instance d'entrée. Au lieu de cela, chaque fois que j'appelleFFFJe reçois retourné une instance aléatoire et une solution. Ainsi, je sais queFFF est en fait capable de résoudre arbitrairement...
Sudoku est un puzzle bien connu qui est connu pour être NP-complet et c'est un cas spécial de problème plus général connu sous le nom de carrés latins. Une solution correcte du carré consiste à remplir chaque ligne et chaque colonne avec des nombres de à condition que chaque nombre apparaisse...
Je ne suis pas sûr de le voir. D'après ce que je comprends, les arêtes et les sommets sont des compléments l'un pour l'autre et il est assez surprenant que cette différence existe. Existe-t-il un bon moyen / rapide / facile de voir qu'en fait, trouver un chemin hamiltonien devrait être beaucoup...
J'ai essayé de chercher en ligne, mais je n'ai trouvé aucune déclaration définitive. Il serait logique pour moi que l'union et l'intersection de deux langues NPC produisent une langue qui n'est pas nécessairement dans NPC. Est-il également vrai que les langages des PNJ ne sont pas fermés sous le...
Récemment, je lis des articles sur la dichotomie . Je ne comprends pas quelle condition peut être qualifiée de dichotomie ? Que signifie «une question est soit en P soit en NP - complète »? (supposons P ≠≠\neq NP ) Par exemple, j'ai connu le théorème de dichotomie de Schaefer, dans lequel une...