Il y a beaucoup de tentatives pour prouver soit ou , et naturellement beaucoup de gens réfléchissent à la question, ayant des idées pour prouver la direction dans laquelle ils veulent aller.P ≠ N PP = N PP=NP\mathsf{P} = \mathsf{NP} P ≠ N PP≠NP\mathsf{P} \neq \mathsf{NP} Je sais qu'il a été prouvé...
J'ai une compréhension de haut niveau du problème et je comprends que s'il était absolument "avéré" d'être vrai avec une solution fournie, cela ouvrirait la porte à la résolution de nombreux problèmes du domaine de l'informatique.P=NPP=NPP=NP Ma question est la suivante: si quelqu'un publiait une...
Existe-t-il des problèmes connus dans (et non dans ) qui ne sont pas terminés? Je crois comprendre qu'il n'y a actuellement aucun problème connu dans ce cas, mais cela n'a pas été exclu comme une possibilité. NPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP} S'il y a un problème qui est (et non ) mais pas...
Lorsque j'expliquais la preuve de Baker-Gill-Solovay qu'il existe un oracle avec lequel nous pouvons avoir, , et un oracle avec lequel nous pouvons avoir à un ami, une question s'est posée pour savoir pourquoi de telles techniques sont mal adaptées pour prouver le problème , et je n'ai pas pu...
Est-il possible que et la cardinalité de soit la même que la cardinalité de ? Ou signifie-t-il que et doivent avoir des cardinalités différentes?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =
Je suis sûr que quelqu'un a pensé à cela avant ou immédiatement rejeté, mais pourquoi la théorie de la dichotomie de Schaefer avec le théorème de Mahaney sur les ensembles clairsemés n'implique-t-elle pas P = NP? Voici mon raisonnement: créer un langage qui est égal à SAT intersecté par un ensemble...
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
Ceci est mon premier article après avoir été un utilisateur passif depuis un certain temps maintenant. Je voudrais poser quelques questions si vous le permettez. Je ne suis pas mathématicien mais ma question concerne le domaine des mathématiques / informatique. En particulier, le problème P vs NP....
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 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....
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...
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
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'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...
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...
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'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...
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...
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....
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