Que signifie la classe de complexité ? Je sais que ⊕ P est la classe de complexité qui contient les langages A pour lesquels il existe une machine de Turing polynomiale à temps non déterministe M telle que x ∈ A si le nombre d'états accepteurs de la machine M sur l'entrée x est impair.⊕ P⊕...
Je viens de lire quelques pages du livre de Sipser Introduction à la théorie du calcul sur le problème de la correspondance postérieure, et je pense que PCP est en fait dans NP. Le certificateur est la suivante : pour une configuration de pile d'entrée concaténer t 1 , t 2 , . . . , t n comme une...
Comment prouver que ? Je cherche juste un tel oracle TM et un langage récursif pour lequel cela vaut. ML(M)=LN PUNE≠ c o N PUNENPA≠coNPA\mathsf{NP}^A \neq \mathsf{coNP}^AMMML ( M) = LL(M)=LL(M) = L Je connais la preuve où vous montrez qu'il y a un oracle tel que et un oracle tel que . J'ai un...
Définition: réduction de Karp Un langage est Karp réductible à un langage B s'il existe une fonction calculable en temps polynomial f : { 0 , 1 } ∗ → { 0 , 1 } ∗ telle que pour chaque x , x ∈ A si et seulement si f ( x ) ∈ B
Une question a été posée à Stack Overflow ( ici ): Compte tenu d' un nombre entier , imprimer toutes les combinaisons possibles des valeurs entières de et qui résolvent l'équation .A , B , C D A 2 + B 2 + C 2 + D 2 = NNNNA,B,CA,B,CA,B,CDDDA2+B2+C2+D2=NA2+B2+C2+D2=NA^2+B^2+C^2+D^2 = N Cette question...
Ci-dessous, supposons que nous travaillons avec une machine de Turing à bande infinie. En expliquant la notion de complexité temporelle à quelqu'un et pourquoi elle est mesurée par rapport à la taille d'entrée d'une instance, je suis tombé sur la revendication suivante: [..] Par exemple, il est...
Je suis curieux de savoir s'il existe des problèmes complets dans la classe de complexité Arthur-Merlin. Le graphique de non-isomorphisme (GNI) semble être l'exemple canonique d'un problème en AM, mais ce n'est probablement pas complet. Je suppose que je me demande aussi si un problème "complet"...
J'essaie de construire une liste d'algorithmes / problèmes qui sont "exceptionnellement utiles", comme dans la résolution de problèmes qui semblent "de nature très exponentielle", mais qui ont un algorithme particulièrement intelligent qui les résout finalement. Exemples de ce que je veux dire:...
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,...
Je me demande cela en se basant sur plusieurs endroits en ligne qui appellent co- un problème ouvert majeur ... mais je ne trouve aucune indication quant à savoir si c'est la même chose que Problème ...N P P = N PNP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf
En lisant certains blogs sur la complexité de calcul (par exemple ici ), j'ai assimilé la notion qu'il est plus facile de décider si deux groupes sont isomorphes que de tester deux graphiques pour l'isomorphisme. Par exemple, sur la page indiquée, il est dit que l'isomorphisme des graphes est un...
Je suis conscient que cela semble une question très stupide (ou trop évidente à énoncer). Cependant, je suis confus à un moment donné. Nous pouvons montrer que P NP=== si et seulement si nous pouvons concevoir un algorithme qui résout une instance donnée de problème dans NP en temps polynomial....
J'ai cette "preuve" très simple pour NP = CoNP et je pense que j'ai fait quelque chose de mal quelque part, mais je ne trouve pas ce qui ne va pas. Est-ce que quelqu'un peut m'aider? Soit A un problème dans NP, et soit M le décideur de A. Soit B le complément, c'est-à-dire que B est dans CoNP....
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...
Nous avons beaucoup de problèmes, comme factorisation, qui sont fortement conjecturé, mais non prouvé, à l'extérieur P. Y a-t- il des questions avec la propriété opposée, à savoir qu'ils sont fortement conjecturé mais pas prouvé être à l' intérieur de
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...
La complétude du coNP implique-t-elle une dureté NP? En particulier, j'ai un problème dont j'ai montré qu'il était coNP-complet. Puis-je prétendre qu'il est NP-difficile? Je me rends compte que je peux revendiquer la dureté coNP, mais je ne sais pas si cette terminologie est standard. Je suis à...
J'ai vu comment XOR-3-SAT est efficacement résoluble (par exemple, voir la section "XOR-satisfiabilité" dans l'entrée Wikipedia pour le problème de satisfiabilité booléenne ). Je me pose une question de base: XOR-k-SAT est-il efficacement résoluble, pour des formules avec des quantités variables de...
Je me demande quelle est la complexité temporelle de la détermination du vide pour les DFA bidirectionnels? Autrement dit, des automates finis qui peuvent reculer sur leur bande d'entrée en lecture seule. Selon Wikipedia, ils sont équivalents aux DFA, bien que les DFA équivalents puissent être...
Ou: Avons-nous besoin de Rupert pour obtenir des cadeaux? Mis à part les problèmes de routage , le Père Noël est confronté au problème suivant (plusieurs fois): Étant donné un sac d'une capacité¹ CCC et un ensemble de cadeaux {p1,…,pn}{p1,…,pn}\{p_1, \dots, p_n\} , chacun de taille sisis_i , il...