Dans le fil Problèmes majeurs non résolus en informatique théorique? Iddo Tzameret a formulé l’excellent commentaire suivant:
Je pense que nous devrions faire la distinction entre les grands problèmes ouverts qui sont considérés comme des problèmes fondamentaux, comme , et les grands problèmes ouverts qui constitueront une avancée technique, s’ils sont résolus, mais ne sont pas nécessairement aussi fondamentaux, par exemple, des limites inférieures exponentielles en mode circuits (c.-à-d. AC ^ 0 + \ mod 6 portes). Nous devrions donc éventuellement ouvrir un nouveau wiki de communauté intitulé "Problèmes ouverts aux frontières du SDC", ou similaire.
Depuis Iddo n'a pas commencé le fil, j'ai pensé que je vais commencer ce fil.
Les chercheurs travaillant dans des domaines connexes connaissent souvent les principaux problèmes en suspens dans des domaines, mais le point de blocage des recherches en cours est inconnu des étrangers. L'exemple cité est un bon exemple. En tant qu'étranger, il est clair que l'un des plus gros problèmes de complexité des circuits est de montrer que NP nécessite des circuits de taille super-polynomiale. Mais les observateurs extérieurs peuvent ne pas se rendre compte que le point actuel où nous sommes bloqués tente de prouver des limites inférieures exponentielles pour les circuits AC 0 à portes mod 6. (Bien sûr, il pourrait y avoir d'autres problèmes de complexité de circuit de difficulté similaire qui décriraient où nous sommes bloqués. Ce n'est pas unique.) Un autre exemple est de montrer les limites inférieures de l'espace-temps pour SAT meilleures que n 1.801 .
Ce fil est pour des exemples comme celui-ci. Comme il est difficile de caractériser de tels problèmes, je donnerai juste quelques exemples de propriétés que de tels problèmes possèdent:
- Ne seront souvent pas les grands problèmes ouverts du terrain, mais constitueront une avancée majeure si elles sont résolues.
- Généralement pas incroyablement difficile, dans le sens où si quelqu'un vous disait que le problème avait été résolu hier, ce ne serait pas trop difficile à croire.
- Ces problèmes auront souvent des nombres ou des constantes qui ne sont pas fondamentaux, mais ils sont dus au fait que c’est là que nous sommes coincés.
- Le problème aux frontières d'un domaine particulier continuera d'évoluer de temps en temps, contrairement au plus gros problème du domaine, qui restera le même pendant de nombreuses années.
- Ces problèmes sont souvent les plus faciles à résoudre. Par exemple, nous n’avons pas non plus de bornes inférieures exponentielles pour AC 1 , mais comme [6] est inclus dans cette classe, il est formellement plus facile de montrer les limites inférieures pour [6], et c’est donc à la frontière actuelle de la complexité du circuit.
Merci de poster un exemple par réponse; les conventions standard de grande liste et CW s'appliquent. Si quelqu'un peut expliquer les types de problèmes que nous recherchons mieux que moi, n'hésitez pas à modifier ce message et à apporter les modifications appropriées.
EDIT: Kaveh a suggéré que les réponses incluent également une explication de la raison pour laquelle un problème donné est à la frontière. Par exemple, pourquoi cherchons-nous des limites inférieures à AC 0 [6] et non à AC 0 [3]? La réponse est que nous avons des limites inférieures contre AC 0 [3]. Mais la question évidente est de savoir pourquoi ces méthodes échouent pour AC 0 [6]. Ce serait bien si les réponses pouvaient aussi expliquer cela.
la source
Réponses:
Voici trois des recherches les plus courtes:
(Les problèmes dirigés sont-ils réellement plus difficiles?)
la source
Ceci est déjà mentionné dans la question:
Ouvert:
Connu:
[Alexander Razborov 1987 - Roman Smolensky 1987] n'est pas dans si est un nombre premier et n'est pas une puissance de .MODm AC0[pk] p m p
[Arkadev Chattopadhyay et Avi Wigderson 2009] Soit m, q des entiers co-premiers tels que m soit sans carrés et possède au plus deux facteurs premiers. Soit C tout circuit de type où est une porte ou et les portes à la base ont des ensembles acceptants arbitraires. Si C calcule alors la fan-in du haut, et donc la taille du circuit, doit être .MAJoGoMODAm G AND OR MODm MODq 2Ω(n)
Ce dernier résultat est basé sur l’obtention d’une borne de corrélation exponentiellement faible de la fonction avec des sous- de profondeur 2 et sur l’estimation des sommes exponentielles impliquant des polynômes de faible degré.MODq
Obstacles: ?
Mise à jour [nov. 10 décembre 2010]
Un article de Ryan Williams semble avoir réglé ce problème ouvert en utilisant des méthodes qui semblent être fondamentalement différentes de celles mentionnées ci-dessus:
Références:
AA Razborov. Limites inférieures de la taille des réseaux de profondeur délimités sur une base complète avec ajout logique (russe), in Matematicheskie Zametki, 41 (4): 598–607, 1987. Traduction anglaise en notes mathématiques de l'Académie des sciences de l'URSS, 41 (4): 333 à 338, 1987.
R. Smolensky. Méthodes algébriques dans la théorie des limites inférieures pour la complexité des circuits booléens. Dans STOC, pages 77–82. ACM, 1987.
Arkadev Chattopadhyay et Avi Wigderson. Systèmes linéaires sur modules composites , FOCS 2009
Ryan Williams. Limites inférieures des circuits de l'ACC non uniformes , 2010, brouillon (soumis?).
la source
Soit CNF-SAT le problème de déterminer si une formule donnée de CNF est satisfaisable (aucune restriction sur la largeur des clauses).
C'est un problème ouvert bien connu dans le domaine des "algorithmes plus rapides pour NP". Je ne pense pas que cela ait atteint le statut de "problème ouvert majeur", mais cela a beaucoup attiré l'attention. Les meilleurs algorithmes connus fonctionnent en temps (par exemple, ici ).2n−Ω(n/log(m/n))
En relation avec l'hypothèse du temps exponentiel (que 3SAT n'est pas dans le temps sous-exponentiel), il existe également une "hypothèse du temps exponentiel fort" selon laquelle le temps d'exécution optimal pour SAT converge vers sous la forme . L'une des conséquences de Strong-ETH serait que la réponse à la question ci-dessus est non. Plusieurs hypothèses plausibles impliquent que la réponse est oui , mais qui sait.k 2n k→∞
Je pense que c'est l'un de ces problèmes qui semblent susceptibles d'être "résolus" d'une manière ou d'une autre: soit nous montrerons une réponse affirmative, soit nous montrerons qu'une réponse affirmative implique quelque chose de très important. Dans le premier cas, nous aurons la satisfaction de résoudre le problème, dans le second, nous aurons élevé la question à celle d'un "problème majeur en suspens" ... une non-réponse implique , et une réponse affirmative implique quelque chose de très important. :)P≠NP
la source
La question de savoir si les arbres de décision peuvent être appris par PAC semble être à la frontière de la théorie de l’apprentissage informatique.
OUVERT
CONNU
La raison pour laquelle il s'agit d'un problème intéressant et important est que les arbres de décision sont une classe très naturelle et, contrairement aux automates, par exemple, nous n'avons pas de résultats de dureté cryptographique qui rendent le problème sans espoir. Les progrès sur cette question peuvent peut-être permettre de savoir si les DT (et des classes similaires) peuvent être appris sans hypothèses de distribution. Cela pourrait avoir un impact pratique en plus d'être une avancée théorique.
Ce problème semble également avoir été abordé de tous les côtés. Nous savons que sous la distribution uniforme dans les exemples: les arbres de décision monotones sont apprenables, que les arbres de décision aléatoires sont apprenables et qu'il existe également une analyse lissée. Nous savons également qu'un algorithme SQ ne résoudra pas ce problème. Et il y a aussi des progrès constants dans ce domaine. D'un autre côté, il s'agit d'un problème difficile qui est ouvert depuis un certain temps. Cela semble donc correspondre au projet de "Problèmes ouverts aux frontières du SDC".
Notez qu'il y a d'autres résultats que je n'ai pas expliqués sur la dureté des DT d' apprentissage appropriées , sur la capacité d' apprendre des DT avec des requêtes et sur la dureté d'apprendre même des DT aléatoires avec des LP.
la source
OUVERT:
Affiche une limite inférieure dans le modèle de sonde de cellule pour un problème explicite de structures de données statiques, ce qui prouve que, dans le cas d'une restriction d'espace "raisonnable" (par exemple, si l'espace est polynomial dans la taille de l'entrée), le temps d'interrogation doit être à moins T, où T est plus grand que log | Q |, où Q est l'ensemble des requêtes. C'est ce qu'on appelle la "barrière | log | Q |" (ou parfois, de façon quelque peu mal nommée, la "barrière de connexion").
CONNU:
bornes inférieures supérieures à log | Q | pour un problème implicite (voir l'enquête de Miltersen )
bornes inférieures supérieures à log | Q | avec des restrictions d'espace extrêmes (par exemple limites inférieures succinctes)
bornes inférieures supérieures à log | Q | pour les problèmes dynamiques (où je veux dire que si le temps de mise à jour est très petit, le temps d'interrogation doit être très grand, ou inversement; voir par exemple la limite inférieure de Patrascu pour la somme partielle)
Limites inférieures dans les modèles restreints, tels que les machines à pointeur, le modèle de comparaison, etc.
bornes inférieures qui cassent le journal | Q | La barrière ne peut pas être prouvée par le type standard de réduction de la complexité de la communication, car Alice peut simplement envoyer la requête elle-même, qui ne prend que log | Q | bits, et il est donc facile de vérifier que la réduction ne donnera jamais une meilleure limite inférieure à celle-ci. Ainsi, il faut soit utiliser un modèle "natif" lié au modèle de sonde cellulaire, soit utiliser une réduction plus intelligente de la complexité de la communication.
la source
Dans les classes de complexité de bas niveau, il y a un problème intéressant concernant la caractérisation de .NL
OUVERT:
CONNU:
INCONNU:
la source
Certains problèmes ouverts du PCP:
Plus formellement: la conjecture est qu'il existe ac, tel que pour tout r naturel, pour tout , il existe un vérificateur PCP qui utilise r le hasard pour faire deux requêtes à sa preuve, a parfait erreur d’intégralité et de justesse . L’alphabet de la preuve ne dépend que de .ε≥2−cr ε 1/ε
Pour deux requêtes, l'erreur la plus connue est pour certains spécifiques (M-Raz, 2008). On peut également obtenir l’erreur pour tout , avec un nombre de requêtes dépendant de (DFKRS).1/rβ β>0 2−rα α<1 α
Les limites inférieures sur c (c'est-à-dire des algorithmes d'approximation) sont également recherchées.
Voir l'enquête de Irit Dinur pour plus de détails.
Plus précisément, nous voulons un vérificateur de la vérifiabilité de la formule SAT comportant un nombre constant de requêtes, un alphabet constant et une erreur constante, et donnant accès à une preuve de longueur linéaire dans la longueur de la formule? Ceci est ouvert même pour les erreurs proches de 1 (mais meilleures que le trivial ), l’alphabet sous-exponentiel et le nombre sous-linéaire de requêtes.1−1/n
La meilleure longueur connue est pour une erreur constante et pour une erreur sous-constante.npolylogn n⋅2(logn)1−β
la source
Montrer que pour tout , il existe un langage dans qui n'a pas de circuits (non uniformes) avec des fils . Rappelons que . C’est-à-dire prouver la limite inférieure du circuit superlinéaire pour un temps exponentiel avec accès à un oracle .c>0 ENP cn E=⋃k≥1TIME[2kn] NP
la source
A - le code décodable localement (LDC) est une carte telle qu'il existe un algorithme , appelé décodeur local , qui donne comme entrée un entier et un mot reçu différent de pour certains au plus fraction de positions, recherche au plus coordonnées de et génère avec une probabilité d'au moins . Le LDC est dit linéaire si(q,δ,ϵ) C:Fm→Fn A i∈[m] y∈Fn C(x) x∈Fm δ q y xi 1/|F|+ϵ F est un champ et est -linear. Les PMA ont, entre autres, de nombreuses applications dans la théorie de la complexité et la protection de la vie privée.C F
Pour et constante , la situation est complètement résolue. Le code Hadamard est un LDC linéaire à interrogations avec , ce qui est connu pour être essentiellement optimal, même pour les LDC non linéaires. Mais ici, est la frontière! Dès que nous obtenons , il y a un énorme fossé entre les limites supérieure et inférieure connues. La meilleure limite supérieure actuelle est un LDC linéaire à requêtes sur tout champ fini (et même les réels et complexes) avec une complexité de requête [ Efremenko '09 , Dvir-Gopalan-Yekhanin '10 ]. La meilleure limite inférieure estq=2 δ,ϵ 2 n=exp(m) q=2 q=3 3 n=exp(exp(logmloglogm−−−−−−−−−−−−√))=2mo(1) Ω(m2) pour les PMA linéaires à interrogations sur n'importe quel champ et pour les PMA généraux à interrogations [ Woodruff '10 ]. La situation pour un plus grand nombre de requêtes est encore plus grave.3 Ω(m2/logm) 3
la source
Quel est le plus grand écart possible entre les complexités d'interrogation quantiques déterministes et (d'erreur à deux côtés) pour les fonctions totales?
Ouvert:
Connu:
On suppose que la fonction OU réalise le plus grand écart possible.Selon la suggestion d'Ashley, permettez-moi d'ajouter le même problème pour un calcul exact.
Ouvert:
Connu:
la source
Il y a un certain nombre de problèmes en suspens dans la complexité des preuves, je n'en mentionnerai qu'un qui reste ouvert même après que des experts ont passé des années à essayer de le résoudre. C'est la version de complexité de preuve de l'état dans la complexité de circuit. (Voir [Segerlind07] si vous voulez voir plus de problèmes ouverts dans la complexité de la preuve.)
Ouvert
Connu
Références:
la source
Ouvert:
Le gros problème qui se pose est de montrer une séparation oracle entre BQP et PH. Mais nous n'avons même pas de séparation entre BQP et AM (puisque AM est dans PH, cela devrait être plus facile). Pire encore, augmentez considérablement la puissance du BQP en autorisant des interactions à un tour avec Merlin, en vous donnant la classe QAM ou QIP (2) (selon les pièces publiques ou privées) et nous n’avons toujours pas de séparation.
Connu:
la source
Je ne suis pas sûr que cela appartienne à la classe des problèmes ouverts frontaliers ou des problèmes ouverts majeurs, alors les commentaires sont les bienvenus.
Ouvert:
Ce problème a été signalé dans le blog Complexity en 2003.
Connu:
Inconnu:
Article connexe: Plus d'informations sur les classes syntaxiques vs sémantiques, et UP vs NP .
la source