Supposons que je considère la variante suivante de BPP, qui appelons E (xact) BPP: Une langue est en EBPP s'il y a un TG aléatoire polynomial qui accepte chaque mot de la langue avec exactement 3/4 de probabilité et chaque mot qui n'est pas dans la langue avec exactement 1/4 de probabilité....
Dans le "dernier paragraphe" de la "première page" de l'article suivant: Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , «If NP Has Polynomial-Size Circuits, then MA = AM», Theoretical Computer Science, 1995. J'ai rencontré une affirmation quelque peu contre-intuitive:...
Récemment, j'ai rencontré la variante suivante de coloration des bords. Étant donné un graphe connexe non orienté, trouvez une coloration des arêtes qui utilise le nombre maximal de couleurs tout en satisfaisant également la contrainte selon laquelle, pour chaque sommet , les arêtes incidentes à...
Suite à la suggestion de Josh Grochow, je convertis mon commentaire d'une question précédente en une nouvelle question. Quelles preuves avons-nous pour ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Ici est la classe de langages reconnaissable par les machines de Turing non déterministes à temps...
Inspiré par une question que m'a posée Greg Kuperberg, je me demande s'il existe des articles qui définissent et étudient les classes de complexité des langues admettant divers types de preuves de connaissances . Les classes comme SZK et NISZK sont extrêmement naturelles du point de vue de la...
J'ai besoin d'une liste de langues complètes. Il y a deux de ces problèmes répertoriés dans le Complexity Zoo , à savoir:Σp2Σ2p\Sigma_2^p DNF équivalent minimum. Étant donné une formule DNF F et un entier k, existe-t-il une formule DNF équivalente à F avec k ou moins d'occurrences de littéraux?...
LogCFL est l'ensemble de toutes les langues qui sont réductibles en espace de journalisation en une langue sans contexte. De même, LogDCFL est l'ensemble de toutes les langues qui sont un espace de journalisation réductible à une langue déterministe sans contexte. Consultez cet article de wikipedia...
Je me demandais si des problèmes pour lesquels existent des algorithmes de temps sublinéaire (dans la taille d'entrée) pouvaient être caractérisés comme possédant des propriétés spécifiques. Cela comprend le temps sublinéaire (par exemple, les tests de propriétés, une autre notion d'approximation...
Quels sont quelques exemples de paires de classes de complexité et B telles queAAABBB on ne sait pas si , etA=BA=BA=B nous ne connaissons pas non plus de relativisations contradictoires (c'est-à-dire que nous ne connaissons pas les oracles et Q tels que A P = B P et A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P...
NP est-il dans DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
Je suis intéressé s'il existe de bons articles ou enquêtes expositifs auxquels je peux me référer lorsque j'écris sur les opérateurs de classes de complexité : des opérateurs qui transforment les classes de complexité en faisant des choses telles que leur ajouter des quantificateurs. Exemples...
Les théorèmes de la hiérarchie sont des outils fondamentaux. Un bon nombre d'entre eux ont été rassemblés dans une question précédente (voir Quelles hiérarchies et / ou théorèmes de hiérarchie connaissez-vous? ). Certaines séparations de classes de complexité découlent directement des théorèmes de...
Nous disons que NFA est constamment ambigu s'il existe telle sorte que tout mot est accepté par ou (exactement) chemins.k ∈ N w ∈ Σ ∗ 0 kMMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Si l'automate est constamment ambigu pour , alors est appelé FA sans ambiguïté (UFA).k = 1 MMMMk=1k=1k=1MMM...
La classe de complexité BQP correspond à des sous-programmes quantiques polynomiaux temporels prenant des entrées classiques et crachant une sortie classique probabiliste. Le conseil quantique le modifie pour inclure des copies de certains états de conseil quantique prédéterminés mais avec des...
Quels sont les problèmes non triviaux où nous savons que l'algorithme actuel que nous avons est asymptotiquement optimal? (Pour les machines de turing) Et comment cela est-il
Il y a eu un travail fantastique sur le permanent en cours au cours des deux dernières décennies et je m'interroge depuis un moment sur la possibilité d'un algorithme Smooth P pour le permanent des matrices non négatives. Il y a bien sûr le fameux algorithme JSV mais c'est un fpras. En pensant à...
Nous considérons souvent les classes de complexité où nous sommes limités dans la quantité d'espace que notre machine de Turing peut utiliser, par exemple: ou NSPACE ( f ( n ) ) . Il semble qu'au début de la théorie de la complexité, il y eut beaucoup de succès avec ces classes telles que le...
En lisant l'article " Une théorie applicative pour la FPH ", vous pouvez rencontrer le passage suivant: Compte tenu des théories qui caractérisent les classes de complexité informatique, il existe trois approches différentes: dans l'un, les fonctions qui peuvent être définies dans la théorie sont...
Question courte. Quelle est la puissance de calcul des circuits "quantiques", si nous autorisons des portes non unitaires (mais toujours inversibles) et exigons que la sortie donne la réponse correcte avec certitude? Cette question concerne en quelque sorte ce qui arrive à la classe lorsque vous...
On dit qu'un problème P est dans APX s'il existe une constante c> 0 telle qu'un algorithme d'approximation polynomiale en temps existe pour P avec le facteur d'approximation 1 + c. APX contient PTAS (vu en choisissant simplement n'importe quelle constante c> 0) et P. APX est-il dans NP? En...