comment montrer la relation entre "Conjecture de jeux uniques" et "Théorème PCP"? comment expliquer que "la conjecture des jeux uniques" est une forme plus forte de "théorème
La méthode de l'adversaire négatif ( ) est un SDP qui caractérise la complexité des requêtes quantiques. Il s'agit d'une généralisation de la méthode de l'adversaire largement utilisée ( ), et surmonte les deux obstacles qui ont entravé la méthode de l'adversaire:A D V±UNEréV±ADV^\pmA D VUNEréVADV...
J'ai récemment lu une preuve qui avait pour but de montrer qu'un problème était fortement NP-difficile, simplement en le réduisant (en temps polynomial) à partir d'un problème fortement NP-difficile. Cela n'avait aucun sens pour moi. J'aurais pensé que vous deviez montrer que tous les nombres...
Taquin Étant donné que le problème est assez long, voici un cas spécial qui capture son essence. Problème: Soit A un algorithme detrministique pour 3-SAT. Est le problème de la simulation complète de l'algorithme A (sur chaque instance du problème). P-Space dur? (Plus précisément, y a-t-il des...
Les graphes planaires ont le genre zéro. Les graphiques embarquables sur un tore ont un genre au maximum 1. Ma question est simple: Y a-t-il des problèmes qui peuvent être résolus polynomialement sur les graphes planaires mais NP-dur sur les graphes du genre un? Plus généralement, y a-t-il des...
J'ai enseigné bornes inférieures aujourd'hui, et l'un des étudiants a demandé la raison du nom . L'explication officielle est que le "A" signifie "Alternance".AC0AC0AC^0ACACAC Je me souviens vaguement, il y a de nombreuses années, que Nick Pippenger Steve Cook a nommé après Nick Pippenger (la...
Version courte. La preuve originale que # 2-SAT est #P -complete montre, en fait, que les instances de # 2-SAT qui sont à la fois monotones (n'impliquant la négation d'aucune variable) et bipartites (le graphique formé par les clauses sur le est un graphe bipartite) sont #P -hard. Ainsi, les deux...
La complexité des circuits en profondeur bornée est l'un des principaux domaines de recherche de la théorie de la complexité des circuits. Cette rubrique a des origines dans des résultats comme "la fonction de parité n'est pas dans " et "la fonction mod n'est pas calculée par ", où est la classe...
Je recherche des exemples naturels d' algorithmes efficaces (ie en temps polynomial) st leur exactitude et leur efficacité peuvent être prouvées de manière constructive (par exemple en ou ), maisPR APRUNEPRAHUNEHUNEHA aucune preuve utilisant uniquement des concepts efficaces n'est connue...
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 à...
Une chose que les ordinateurs quantiques peuvent faire (peut-être même avec seulement des circuits quantiques BPP + log-depth) est d'échantillonner approximativement la transformée de Fourier d'une fonction booléenne évaluée en P.±1±1\pm 1 Ici et ci-dessous quand je parle d'échantillonner la...
Considérons le problèmeQQQ suivant Q : On nous donne un entier et k intervalles [ l i , r i ] avec 1 ≤ l i ≤ r i ≤ 2 n . On nous donne également 2 n entiers d 1 , … , d 2 n ≥ 0 . La tâche consiste à sélectionner un nombre minimum d'intervalles [ l i , r i
Lorsqu'on essaie de convaincre les économistes de la pertinence de la théorie de la complexité dans la presse écrite, existe-t-il une référence standard à citer? Je connais le billet de blog de Noam Nisan , l'enquête de Tim Roughgarden et le chapitre 11 de l'essai de Scott Aaronson . Ces articles...
Je fais une revue de la littérature sur le problème d'isomorphisme graphique. La plupart des articles que je lis sont écrits par EM Luks et Laszlo Babai. Ces articles utilisent les connaissances de haut niveau de la théorie des groupes et de la théorie de la complexité. Comme je suis nouveau dans...
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é....
En recherchant le système d'information sur les classes de graphes et leurs inclusions , j'ai trouvé plusieurs classes de graphes pour lesquelles le problème du cycle hamiltonien est NP-complet alors que la complexité des problèmes de chemin hamiltonien n'est PAS connue. Certaines de ces classes...
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...
L'article "Algorithmes sous-quadratiques pour 3SUM", par Ilya Baran, Erik D. Demaine, Mihai Patrascu a la complexité suivante pour le Problème 3SUM: étant donné une liste LLL de nnn entiers s'il y a x,y,z∈Lx,y,z∈Lx,y,z \in L tels que x+y=z.x+y=z.x+y=z. w−w−w-A C 0 O ( n 2 / w 2 log w ) O ( n 2 / (...
On sait que la taille minimale des U_2 calculant la fonction de parité est exactement égale à . La preuve de la borne inférieure est basée sur la méthode d'élimination des portes.U2U2U_23 ( n - 1 )3(n-1)3(n-1) Récemment, j'ai remarqué que la méthode d'élimination de porte fonctionne bien également...
Étant donné le groupe de symétrie et deux sous-groupes et , ? G , H ≤ S n π ∈ S n G π ∩ H = ∅SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset Pour autant que je sache, le problème est connu sous le nom de problème d'intersection de coset. Je me demande quelle est la...