Pour raisonner sur des choses comme l'exhaustivité de NP, nous utilisons généralement plusieurs réductions (c.-à-d. Des réductions de Karp). Cela conduit à des images comme celle-ci: (sous conjectures standard). Je suis sûr que nous connaissons tous ce genre de choses. Quelle image obtenons-nous si...
Si alors la hiérarchie s'effondre à son deuxième niveau (par le théorème de Karp-Lipton). Mais qu'en est-il de N P et de c o N P ?RP=NPRP=NP\sf RP = NPNPNP\sf NPcoNPcoNP\sf coNP J'ai essayé de prouver que est contenu dans N P (l'autre sens est trivial si R P = N P ) mais en vain, et je ne suis même...
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...
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'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...
Je suis confus quant à la façon dont PP et BPP sont définis. Supposons χχ\chi est la fonction caractéristique d'un langage LL\mathcal{L} . M être la machine de Turing probabiliste. Les définitions suivantes sont-elles correctes: P P = { L : P r [ χ ( x ) ≠ M ( x ) ] >...
Supposer ΠΠ\Pi est un problème de décision décidable. Est-ce que Π ∉ NPΠ∉NP\Pi\not \in NP impliquer ΠΠ\Pi est NPNPNP-Difficile? Edit: si l'on suppose qu'il existe Π ∈ c o NP∖ NPΠ∈coNP∖NP\Pi\in coNP\setminus NPalors nous avons terminé. Pouvons-nous réfuter la réclamation sans hypothèses...
La classe de Nick (NC) est la classe de problèmes qui peuvent être résolus en temps poly-log en utilisant un nombre polynomial de processeurs. Je veux en savoir plus sur l'analogue exponentiel, qui couvrirait les problèmes qui peuvent être résolus en temps polynomial en utilisant un nombre...
Lorsque le célèbre théorème de Savitch est énoncé, on voit souvent l'exigence que soit constructible dans l'espace (ce qui est intéressant, il est omis dans Wikipedia). Ma question simple est: pourquoi en avons-nous besoin? Je comprends l'exigence que soit dans , ce qui ressort clairement de la...
Je n'ai pas pu trouver de graphique décrivant ou de texte répondant à la question suivante: Existe-t-il une relation directe entre la complexité d'un algorithme (tel que le meilleur / pire cas de tri rapide) et la classe d'automates qui peuvent implémenter l'algorithme. Par exemple, existe-t-il une...
Je pense que ces deux classes devraient être les mêmes, mais je ne trouve aucune littérature à ce sujet et j'ai une formation limitée sur le sujet. C'est mon raisonnement, et je voudrais savoir si (1) cela est déjà connu ou (2) j'ai mal compris quelque chose ou (3) je viens de découvrir quelque...
Existe-t-il un problème de décision dans une classe de complexité correctement incluse dans DLOGTIME? (saufO ( 1 )O(1)O(1), bien sûr) Si tel est le cas, pouvons-nous créer des problèmes complets pour DLOGTIME? Alors, peut-il y avoir une réduction deO ( log( journaln )