La parité et sont comme des jumeaux inséparables. Ou du moins, cela semble au cours des 30 dernières années. À la lumière du résultat de Ryan, il y aura un regain d'intérêt pour les petites classes.AC0AC0AC^0 Furst Saxe Sipser à Yao à Hastad sont toutes des restrictions de parité et aléatoires....
Peut-on calculer une porte de seuil à bits par des circuits de taille polynomiale (fan-in illimité) de profondeur lg nnnn ? Alternativement, pouvons-nous compter le nombre de 1 dans les bits d'entrée en utilisant ces circuits?lgnlglgnlgnlglgn\frac{\lg n}{\lg \lg n} Est ?T C0⊆ A l t T i m e (O(...
Prédire la bourse est difficile! TCS peut-il rendre ce sentiment plus formel? Récemment, j'ai commencé à réfléchir un peu à la finance et je me demandais en quoi la connaissance du TCS pouvait aider. Les fonds spéculatifs et les sociétés d'investissement semblent utiliser le trading algorithmique,...
EDIT au 2011/02/08: Après avoir trouvé et lu des références, j'ai décidé de séparer la question d'origine en deux questions distinctes. Voici la partie concernant UP vs NP, pour la partie classes syntaxiques et sémantiques, veuillez consulter Avantages pour les classes syntaxiques et sémantiques ....
Je suis intéressé par la complexité de la résolution d'équations linéaires modulo k , pour k arbitraire (et avec un intérêt particulier pour les puissances premières), en particulier: Problème. Pour un système donné de équations linéaires dans n modules inconnus k , existe-t-il des...
Mon théorème préféré en théorie de la complexité est le théorème de la hiérarchie temporelle. Cependant, cela a été fait en 1965. Je voulais alors savoir s'il y avait quelque chose de similaire pour l'informatique quantique. Si ce n'est pas le cas, quelles sont les personnes / groupes qui...
Soit le pire temps d'exécution d'un problème sur une entrée de taille n . Faisons un peu bizarre le problème en fixant f ( n ) = n 2 pour n = 2 k mais f ( n ) = n pour n = 2 kf(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = n .n=2k+1n=2k+1n=2k+1 Alors, quelle est la limite...
Y a-t-il des références qui fournissent des détails sur les limites inférieures du circuit pour des problèmes difficiles spécifiques survenant en cryptographie tels que l'affacturage entier, problème de logarithme discret premier / composite et sa variante sur un groupe de points de courbes...
Il semble connu que pour trouver une réponse à une requête sur une base de données relationnelle D , il faut du temps | D | | Q | , et on ne peut pas se débarrasser de l'exposant | Q | .QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Comme peut être très volumineux, nous nous demandons pourquoi les bases de...
La parité-P est l'ensemble des langages reconnus par une machine de Turing non déterministe qui ne peut distinguer qu'un nombre pair ou un nombre impair de chemins "d'acceptation" (plutôt qu'un nombre nul ou non nul de chemins d'acceptation). Ainsi la parité-P est essentiellement PP jeune frère...
Toutes les fonctions dont le poids de Fourier est concentré sur les ensembles de petite taille (ou termes de faible degré) sont-elles calculées par les circuits ?A
La célèbre conjecture d'isomorphisme de Berman et Hartmanis dit que tous langages complets sont isomorphes en temps polynomiaux (p-isomorphes) les uns aux autres. La signification clé de la conjecture est qu'elle implique . Il a été publié en 1977, et une preuve à l'appui était que tous problèmes...
IP = PSPACE est répertorié comme l'exemple canonique d'un résultat non relativisant, et la preuve en est qu'il existe un oracle OOO tel que , tandis que {\ sf coNP} ^ O \ subseteq {\ sf PSPACE} ^ O pour tous oracles O .c o N P O ⊆ P S P A C E O OcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf...
Je suis intéressé par une fonction booléenne explicite avec la propriété suivante: si est constant sur un sous-espace affine de , alors la dimension de ce sous-espace est .f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}fff0,1n0,1n\\{0,1\\}^no(n)o(n)o(n) Il n'est pas difficile de...
Mafia est un jeu de rôle populaire lors des fêtes, une description détaillée est disponible sur wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Fondamentalement, cela fonctionne comme suit: Au début, chacun des joueurs se voit secrètement assigner un rôle, soit aligné avec la mafia soit...
Que sait-on de la complexité exacte du problème de chaîne la plus courte? Peut-il être résolu plus rapidement que ? Existe-t-il des algorithmes connus qui résolvent la super chaîne la plus courte sans réduire au TSP?O∗(2n)O∗(2n)O^*(2^n) UPD: supprime les facteurs polynomiaux.O∗(⋅)O∗(⋅)O^*(\cdot) Le...
Je pense que ce serait une bonne idée de faire une liste de théorèmes indiquant que P n'est pas égal à NP si et seulement si telle ou telle sortie, une classe de complexité est contenue dans une autre classe de complexité et ainsi de suite et ainsi de suite.
Je m'intéresse au problème suivant: étant donné une matrice , y a-t-il un graphe non orienté sur n sommets dont la matrice d'adjacence au carré est cette matrice?n × nn×nn\times nnnn La complexité de calcul de ce problème est-elle connue? Remarques: Bien sûr, cela peut aussi être formulé comme un...
Soit une formule CNF satisfaisante avec n variables et m clauses. Soit S F 1 l'espace de solution de F 1 .F1F1F_1nnnmmmSF1SF1S_{F_1}F1F1F_1 Considérons le problème de déterminer, étant donné , une autre formule CNF F 2 avec le même ensemble de variables que F 1 , avec S F 2 = S F 1 (même espace de...
Ai-je raison de comprendre que prouver un problème NP complet est un succès en recherche? Si oui,