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....
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
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 sais que c'est idiot, mais j'ai réussi à me confondre et j'ai besoin d'aide pour régler ça Supposons que , alors clairement pour chaque oracle nous avons qui contredit le fait qu'il existe un oracle pour lequel , d'oùP= NPP=NPP=NPUNEUNEAPUNE= NPUNEPUNE=NPUNEP^A=NP^AUNEUNEAPUNE≠...
J'ai un problème et je suppose que c'est NP-difficile, mais je ne peux pas le prouver. Voici un graphique de calque, où le calque 0 est le calque le plus chaud et le calque L le plus bas. il y a un bord dirigé entre les couches, où un bord (A, B) indique que le nœud A peut [couvrir] le nœud B. Et...
J'essaie de faire valoir que N n'est pas égal à NP en utilisant des théorèmes de hiérarchie. C'est mon argument, mais quand je l'ai montré à notre professeur et après déduction, il a dit que c'était problématique où je ne trouvais pas de raison impérieuse d'accepter. Nous commençons en supposant...
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...
J'aimerais vraiment votre aide pour prouver ce qui suit. Si alors .NTime(n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})P=NPP=NP\mathrm{P}=\mathrm{NP} Ici, est la classe de toutes les langues qui peut être décidée par la machine de Turing non...
Si P = N PP=NP\mathbf{P} = \mathbf{NP} , alors L = N LL=NL\mathbf{L} = \mathbf{NL} ? Je pose cette question parce que, pour d'autres classes non déterministes, il semble que P = N PP=NP\mathbf{P} = \mathbf{NP} établit toujours qu'elles sont égales à leurs homologues
J'ai récemment lu une entrée de blog très intéressante de Google Research Blog sur le réseau neuronal. Fondamentalement, ils utilisent ces réseaux de neurones pour résoudre divers problèmes comme la reconnaissance d'image. Ils utilisent des algorithmes génétiques pour "faire évoluer" les poids des...
Cette question est en quelque sorte l'inverse d' une question précédente sur les ensembles formés à partir d'opérations sur les ensembles NP-complets: Si l'ensemble résultant de l'union, de l'intersection ou du produit cartésien de deux ensembles décidables et L 2 est NP-complet, au moins l'un de L...
Valiant et Vazirani ont prouvé que la SAT est réductible à la SAT UNIQUE sous des réductions probabilistes randomisées du temps polynomial. Calabro et al . a montré que UNIQUE k-SAT est aussi dur que k-SAT. Maintenant, la question est, si quelqu'un montre que k-SAT UNIQUE est dans P, cela...
Est-ce que le 2 dans un algorithme à 2 approximations signifie que la solution est dans 2 * OPT ou OPT /
Nous venons donc d'apprendre sur l'auto-réductibilité en classe. Mon professeur et notre manuel ne s'engageraient pas à dire que tous les problèmes de NP sont auto-réductibles, mais il ne semble pas y avoir d'exemples de problèmes qui ne le soient pas. Je me demandais s'il y avait des exemples, ou...
Y a-t-il une classe de problèmes NP qui ont une solution unique? C'est ce que je demande, parce que lorsque j'étudiais la cryptographie, j'ai lu sur le sac à dos et j'ai trouvé l'idée très
J'aimerais votre aide pour prouver que la langue est décidable ssi .L = { ⟨ M⟩ | L ( M) ∈ N P ∖ P }L={⟨M⟩|L(M)∈NP∖P}L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}P = N PP=NP\mathrm{P}=\mathrm{NP} Si , je comprends que c'est le langage des machines Turing vides....
J'ai récemment imaginé la preuve suivante que L = P implique P = NP. Supposons que L = P. Soit A un problème dans NP. Selon la définition du vérificateur de NP, chaque solution positive à A a un témoin qui peut être vérifié en temps polynomial. Puisque P = L, la même solution peut être vérifiée...
Peut-être que je manque quelque chose d'évident, mais est-ce que P = co-NP NP ou vice versa? Mon sentiment est qu'il doit y avoir un théorème qui exclut cette
Je suis sûr qu'il doit y avoir quelque chose qui ne va pas dans le raisonnement suivant, car sinon beaucoup de recherches P vs NP seraient réduites mais je ne peux pas déterminer mon erreur: Pour tout entier fixe définissezk > 0k>0k>0Bk: = { ⟨ & Phiv ⟩ |φest un wff de ZF et a une preuve...
Donc représente les problèmes où nous avons de petits témoins vérifiables pour les instances et pour les petits témoins vérifiables pour les instances . Comment ça marche pourNPNPNPYESYESYEScoNPcoNPcoNPNONONO PNPPNPP^{NP} NPNPNPNPNP^{NP} coNPNPcoNPNPcoNP^{NP} etc?