Problèmes majeurs non résolus en informatique théorique?

Wikipedia n'énumère que deux problèmes sous "problèmes non résolus en informatique" :

• P = NP?
• L'existence de fonctions à sens unique

Quels sont les autres problèmes majeurs qui devraient être ajoutés à cette liste?

Règles:

1. Un seul problème par réponse
2. Fournir une brève description et tout lien pertinent

Peut-on multiplier par matrices en opérations ?n O ( n 2$n$$n$$O(n^2)$

L'exposant de la borne supérieure la plus connue a même un symbole spécial, . Actuellement, est approximativement à 2.376, selon l’ algorithme Coppersmith-Winograd . Un bel aperçu de l'état de l'art est Sara Robinson, Vers un algorithme optimal pour Matrix Multiplication , SIAM Nouvelles, 38 (9), 2005.$\omega$$\omega$

Mise à jour: Andrew Stothers (dans sa thèse de 2010 ) a montré que avait été amélioré par Virginia Vassilevska Williams ( pré-impression de juillet 2014 ) en . Ces limites ont été obtenues par une analyse minutieuse de la technique de base de Coppersmith-Winograd.ω < $\omega < 2.3737$$\omega < 2.372873$

Mise à jour ultérieure (30 janvier 2014): François Le Gall a prouvé que dans un article publié dans ISSAC 2014 ( préimpression arXiv ).$\omega < 2.3728639$

L'isomorphisme graphique est-il en P?

La complexité de l’isomorphisme graphique (IG) est une question ouverte depuis plusieurs décennies. Stephen Cook en a parlé dans son document de 1971 sur la NP-complétude de la SAT .

Déterminer si deux graphes sont isomorphes peut généralement être fait rapidement, par exemple avec un logiciel tel que nautyet saucy. En revanche, Miyazaki a construit des classes d'instances pour lesquelles il est nautyprouvé qu'il faut un temps exponentiel.

Read et Corneil ont passé en revue les nombreuses tentatives faites jusqu'à présent pour s'attaquer à la complexité de l'IG: La maladie de l'isomorphisme des graphes , Journal of Graph Theory 1 , 339–363, 1977.

On ne sait pas que GI est en co-NP, mais il existe un protocole aléatoire simple pour le non-isomorphisme de graphique (RNB). Donc, on pense donc que GI (= co-RNB) est "proche de" NP co.${}\cap{}$

D'autre part, si GI est NP-complet, la hiérarchie polynomiale s'effondre. Il est donc peu probable que l'IG soit complet. (Boppana, Håstad, Zachos, est- ce que le co-NP a de courtes preuves interactives?, IPL 25 , 127–132, 1987)

Shiva Kintali a une belle discussion de la complexité de GI sur son blog.

Laszlo Babai a prouvé que l' isomorphisme des graphes est dans le temps sous-exponentiel .

Complexité de l'affacturage

La factorisation est-elle dans ?$\mathsf{P}$

• Conséquences de l'affacturage dans P?
• Les problèmes PRIMES, FACTORING sont-ils connus pour être P-dur?
• Quelles sont les conséquences de l'affacturage étant NP-complet?
• P avec factorisation entière oracle
• La preuve de la factorisation de nombre entier est en P (sur MO )

P = BPP?

Existe-t-il une règle pivot pour l'algorithme simplex qui donne le temps d'exécution polynomial dans le cas le plus défavorable? Plus généralement, existe-t-il un algorithme fortement polynomial pour la programmation linéaire?

L’ hypothèse de temps exponentiel (ETH) affirme que la résolution de SAT nécessite un temps exponentiel de 2 ^{Ω (n)} . ETH implique beaucoup de choses, par exemple que SAT n'est pas dans P, donc ETH implique P ≠ NP. Voir Impagliazzo, Paturi, Zane, Quels problèmes ont une complexité fortement exponentielle? , JCSS 63, 512–530, 2001.

On pense généralement que l’ETH est difficile à prouver car il implique de nombreuses autres séparations de classes de complexité.

Immerman et Vardi montrent que la logique en virgule fixe capture PTIME dans la classe des structures ordonnées . L'un des plus gros problèmes en suspens dans la théorie descriptive de la complexité est de savoir si la dépendance à l'ordre peut être supprimée:

Existe-t-il une logique qui capture PTIME?

En termes simples, une logique capturant PTIME est un langage de programmation pour les problèmes de graphes qui fonctionne directement sur la structure du graphe et qui n’a pas accès au codage des sommets et des arêtes, de sorte que les éléments suivants sont conservés:

1. tout programme syntaxiquement correct modélise un problème de graphe calculable en temps polynomial et
2. tout problème de graphe calculable en temps polynomial peut être modélisé par un programme syntaxiquement correct.

S'il n'y a pas de logique qui capture PTIME, alors puisque NP est capturé par la logique de second ordre existentielle. Une logique capturant PTIME fournirait une attaque possible à P vs NP.$P \neq NP$

Voir le blog de Lipton pour une discussion informelle et M. Grohe: La quête d'une logique de capture de PTIME (LICS 2008) pour un aperçu plus technique.

La conjecture des jeux uniques est-elle vraie?
Et: étant donné qu’il existe des algorithmes d’approximation temporelle sous-exponentielle pour Unique Games , où se situe le problème en terme de complexité?

Permanent versus déterminant

La question permanente versus déterminante est intéressante en raison de deux faits. Premièrement, le permanent d’une matrice compte le nombre d’appariements parfaits dans un graphe bipartite. Par conséquent, le permanent d'une telle matrice est # P-Complete. Dans le même temps, la définition du permanent est très proche de celle du déterminant, finalement différente uniquement à cause d'un simple changement de signe. Il est bien connu que les calculs de déterminant sont en P. On étudie la différence entre le déterminant permanent et le déterminant et le nombre de calculs de déterminant nécessaires pour calculer le discours permanent sur P par rapport à #P.

Peut-on calculer la FFT en beaucoup moins que temps?$O(n \log n)$

Dans la même veine (très) générale, il existe de nombreuses questions concernant l'amélioration des temps d'exécution de nombreux problèmes classiques ou algorithmes: par exemple, peut - on résoudre le chemin le plus court total (APSP) dans temps?$O(n^{3-\epsilon})$

Edit: APSP s'exécute dans le temps "où les additions et les comparaisons de réels sont à coût unitaire (mais toutes les autres opérations ont coût logarithmique) ": http://arxiv.org/pdf/1312.6680v2.pdf$(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$

La conjecture d'optimalité dynamique pour les arbres évasés.

Ou plus généralement: Y a-t-il un arbre de recherche binaire dynamique en ligne concurrentiel?

Un algorithme déterministe temporel linéaire pour le problème du Spanning Tree minimum .

NP versus co-NP

La question NP versus co-NP est intéressante car NP ≠ co-NP implique P ≠ NP (car P est fermé sous complément). Elle concerne également la "dualité": séparation entre trouver / vérifier des exemples et trouver / vérifier des contre-exemples. En fait, prouver que la question est à la fois NP et co-NP constitue notre première preuve irréfutable qu'un problème qui semble être en dehors de P n'est pas non plus NP-complet.

Existe-t-il des problèmes qui ne peuvent pas être résolus efficacement par des ordinateurs parallèles?

Les problèmes qui sont P-complets ne sont pas connus pour être parallélisables. Les problèmes P-complets incluent Horn-SAT et la programmation linéaire. Mais pour prouver que tel est le cas, il faudrait séparer certaines notions de problèmes parallélisables (telles que NC ou LOGCFL) de P.

Les concepteurs de processeurs informatiques augmentent le nombre d'unités de traitement, dans l'espoir d'améliorer les performances. Si des algorithmes fondamentaux tels que la programmation linéaire ne sont par nature pas parallélisables, les conséquences en seront lourdes.

Est-ce que toutes les tautologies propositionnelles ont des preuves de Frege de taille polynomiale?

On peut soutenir que le principal problème ouvert de la complexité des preuves est de démontrer les limites inférieures de taille super-polynomiales sur les preuves propositionnelles (également appelées preuves de Frege).

De manière informelle, un système de preuve Frege est juste un système de preuve propositionnel standard pour prouver des tautologies propositionnelles (on apprend dans un cours de base en logique), ayant des axiomes et des règles de déduction, où les lignes de contrôle sont écrites sous forme de formules. La taille d'une preuve Frege est le nombre de symboles nécessaires pour écrire la preuve.

Le problème demande alors s’il existe une famille de formules tautologiques propositionnelles pour lesquelles il n’existe pas de polynôme tel que la taille minimale de la preuve de Frege de soit au maximum , pour tout (où désigne la taille de la formule ).$(F_n)_{n=1}^\infty$$p$$F_n$$p(|F_n|)$$n=1,2,\ldots$$|F_n|$$F_n$

Définition formelle d'un système à l'épreuve de Frege

Définition (règle Frege) Une règle Frege est une séquence de formules propositionnelles , pour , écrit sous la forme . Dans le cas où , la règle de Frege est appelée un schéma axiome . Une formule est dite dérivée par la règle de si sont toutes des instances de substitution de , pour une affectation aux variables (c'est-à-dire, il y a des formules $A_0(\overline x),\ldots,A_k(\overline x)$$k \le 0$$\frac{A_1(\overline x), \ldots,A_k(\overline x)}{A_0(\overline x)}$$k = 0$$F_0$$F_1,\ldots,F_k$$F_0,\ldots,F_k$$A_1,\ldots,A_k$$\overline x$$B_1,\ldots,B_n$ tels que pour tout . La règle de Frege est dite saine si, chaque fois qu’une assignation satisfait les formules du côté supérieur , elle satisfait également la formule du côté inférieur .$F_i = A_i(B_1/x_1,\ldots,B_n/x_n),$$i=0,\ldots,k$$A_1,\ldots,A_k$$A_0$

Définition (preuve de Frege) Étant donné un ensemble de règles de Frege, une preuve de Frege est une séquence de formules telle que chaque ligne de vérification est un axiome ou a été dérivée par l’une des règles de Frege données à partir de lignes de vérification précédentes. Si la séquence se termine par la formule , alors la preuve est considéré comme une preuve de . La taille d'une épreuve Frege est la taille totale de toutes les formules de l'épreuve.$A$$A$

Un système de preuve est dit implicationally complet si pour tout ensemble de formules , si implique sémantiquement , alors il y a une preuve de en utilisant axiomes (éventuellement) de . Un système de preuve est dit bon s'il admet des preuves de tautologies (quand on n'utilise pas d'axiomes auxiliaires, comme dans le ci-dessus).$T$$T$$F$$F$$T$$T$

Définition (système de preuve Frege) Soit un langage propositionnel et un ensemble fini de règles de Frege sonores, on dit que est un système de preuve Frege si est implicitement complet.$P$$P$$P$

Notez qu'une preuve Frege est toujours bonne, car les règles Frege sont supposées être bonnes. Nous n'avons pas besoin de travailler avec un système spécifique à l'épreuve Frege, car un résultat de base de la preuve indique que tous les deux systèmes à l'épreuve Frege, même dans des langues différentes, sont polynômes. [Reckhow, thèse de doctorat, Université de Toronto, 1976].

L'établissement de limites inférieures sur les preuves Frege pourrait être considéré comme une étape vers la preuve de , car si cela est vrai, aucun système de preuve propositionnelle (y compris Frege) ne peut avoir de preuves de taille polynomiale pour toutes les tautologies.$NP \neq coNP$

Peut-on calculer la distance d'édition entre deux chaînes de longueur en temps sub-quadratique, c'est-à-dire en temps pour un certain ?$n$$O(n^{2-\epsilon})$$\epsilon>0$

Existe-t-il des algorithmes temporels réellement sous-quadratiques (signifiant pour une constante constante pour les problèmes 3SUM-hard ?$O(n^{2-\delta})$$\delta>0$

En 2014, Grønlund et Pettie ont décrit un algorithme déterministe pour 3SUM lui-même, qui s'exécute dans le temps . Bien qu’il s’agisse d’un résultat majeur, l’amélioration par rapport à n’est que (sub) logarithmique. De plus, aucun algorithme sous-quadratique similaire n'est connu pour la plupart des autres problèmes de 3SUM-hard.O ( n 2$O(n^2/(\log n/\log \log n)^{2/3})$$O(n^2)$

BQP = P?

Aussi: NP contenu dans BQP?

Je sais que cela a violé les règles en ayant deux questions dans la réponse, mais quand on prend la question P vs NP, ce ne sont pas nécessairement des questions indépendantes.

1. Conjecture d'isomorphisme. (Tous les problèmes NP-complets sont-ils le "même" problème?)
2. La cryptographie peut-elle être basée sur un problème NP-complet?

et un peu plus loin du grand public:


3. Quelle est la taille de NP dans EXP?

(Officieusement, si vous rencontrez tous les problèmes liés à EXP sur une table et que vous en prenez un uniformément au hasard, quelle est la probabilité que le problème que vous avez choisi soit également défini sur NP? Cette question a été formalisée par la notion de mesure liée aux ressources. On sait que P a une mesure de zéro dans EXP, c’est-à-dire que le problème que vous avez relevé dans le tableau n’est presque pas dans P.)

Quelle est l'approximabilité de Metric TSP ? L'algorithme de Christofides de 1975 est un algorithme d'approximation en temps polynomial (3/2). Est-ce NP-difficile de faire mieux?

• Le TSP métrique se situant dans les limites d’un facteur inférieur à 220/219 est NP-difficile (Papadimitriou et Vempala, 2006 [PS] ). À ma connaissance, il s'agit de la limite inférieure la plus connue.

• Certaines preuves suggèrent que la limite réelle pourrait être de 4/3 (Carr et Vempala, 2004 [Version gratuite] [Bonne version] ).

• La limite supérieure de l'approximabilité a récemment été abaissée à (Mucha 2011, "Approche 13/9 pour TSP graphique" [ PDF ]).$13/9$

Donne une fonction explicite avec une complexité de circuit exponentielle.

Shannon a prouvé en 1949 que si vous choisissez une fonction booléenne au hasard, elle présente une complexité de circuit exponentielle avec une probabilité proche de une.

La meilleure limite inférieure pour une fonction booléenne explicite nous avons jusqu’à présent est de K. Iwama, O. Lachish, H Morizumi et R. Raz.$f:\{0,1\}^n \to \{0,1\}$$5n - o(n)$

Quelle est la complexité de la requête de test de l' absence de triangle dans des graphes denses (c'est-à-dire, distinguer les graphes sans triangle de ceux far de leur absence de triangle)? La borne supérieure connue est une tour d'exponentielles dans , tandis que la limite inférieure connue n'est que légèrement superpolynomiale dans . C’est une question assez fondamentale dans la combinatoire additive théorie des graphes extrêmes / ouverte depuis près de 30 ans.$\epsilon$$1/\epsilon$$1/\epsilon$

Séparez NEXP de BPP. Les gens ont tendance à croire que BPP = P, mais personne ne peut séparer NEXP de BPP.

Je sais que le PO n’a demandé qu’un seul problème par publication, mais les conférences RTA (Techniques de réécriture et leurs applications) 1 et TLCA (Typed Lambda Calculi et leurs applications) maintiennent des listes de problèmes en suspens 2 . Ces listes sont très utiles car elles contiennent également des indications sur des travaux antérieurs visant à résoudre ces problèmes.

Déromérisation du problème de test d'identité polynomiale

Le problème est le suivant: Soit un circuit arithmétique calculant un polynôme , est-ce que est identique à zéro?$P$$P$

Ce problème peut être résolu en temps polynomial randomisé, mais on ne sait pas qu'il est possible de le résoudre en temps polynomial déterministe.

Relatif est conjecture Shub et Smale . Étant donné un polynôme , nous définissons sa complexité comme la taille du plus petit circuit arithmétique calculant utilisant la seule constante . Pour un polynôme univarié , soit le nombre de ses racines réelles.$\tau$$P$$\tau$$\tau(P)$$P$$1$$P\in\mathbb Z[x]$$z(P)$

Prouver qu'il existe une constante universelle telle que pour tout , .P ∈ Z [ x ] z ( P ) ≤ ( 1 + τ ( P ) ) $c$$P\in\mathbb Z[x]$$z(P)\le (1+\tau(P))^c$

Existe-t-il un théorème Quantum PCP?

Il y a beaucoup de problèmes en suspens dans les calculs lambda (dactylographiés et non typés). Voir la liste des problèmes en suspens de la TLCA pour plus de détails. il y a aussi une belle version PDF sans les cadres.

J'aime particulièrement le problème n ° 5:

Existe-t-il des termes non typables dans mais à l'aide de types récursifs positifs?$F_ω$

Le problème du logarithme discret est-il dans P?

Soit soit un groupe cyclique d'ordre et tel que est un générateur de . Le problème de trouver tel que est connu sous le nom de problème de logarithme discret (DLP). Existe-t-il un algorithme (classique) pour résoudre le DLP en temps polynomial dans le cas le plus défavorable en nombre de bits de ?q g , h ∈ G g G n ∈ N g n = h $G$$q$$g,h \in G$$g$$G$$n \in \mathbb{N}$$g^n = h$$q$

Il existe des variantes de DLP que l’on pense plus simples, mais qui ne sont pas encore résolues. Le problème informatique Diffie-Hellman (CDH) demande de trouver donné et . Le problème décisionnel de Diffie-Hellman (DDH) demande de décider, étant donné , si . g , g a g b g , g a , g b , h ∈ $g^{a b}$$g, g^a$$g^b$$g, g^a, g^b, h \in G$$g^{a b} = h$

Clairement, DLP est difficile si CDH est difficile, et CDH est difficile si DDH est difficile, mais aucune réduction réciproque n'est connue, à l'exception de certains groupes. L'hypothèse selon laquelle DDH est difficile est la clé de la sécurité de certains cryptosystèmes, tels que ElGamal et Cramer-Shoup .

Les jeux de parité sont des jeux de graphes d'une durée infinie pour deux joueurs, dont le problème de décision naturel est NP et co-NP, et dont le problème de recherche naturel est dans PPAD et PLS.

http://en.wikipedia.org/wiki/Parity_game

Les jeux de parité peuvent-ils être résolus en temps polynomial?

(Plus généralement, une question ouverte de longue date en programmation mathématique consiste à savoir si les problèmes de complémentarité linéaire à matrice P peuvent être résolus en temps polynomial?)

La zone de complexité paramétrée a sa propre charge de problèmes ouverts.

Considérez les problèmes de décision

• étant donné existe-t-il une couverture de sommet de taille pour le graphe ?$(G,k)$$k$$G$
• étant donné existe-t-il une affectation satisfaisante du poids pour la formule ?$(F,k)$$k$$F$
• étant donné existe-t-il une clique de taille dans un graphe ?$(G,k)$$k$$G$
• etc...

Beaucoup, BEAUCOUP, de problèmes combinatoires existent sous cette forme. La complexité paramétrée considère un algorithme comme "efficace" si son temps d'exécution est lié par la limite supérieure de où est une fonction arbitraire et est une constante indépendante de . En comparaison, notez que tous ces problèmes peuvent être facilement résolus en .$f(k)n^c$$f$$c$$k$$n^{O(k)}$

Ce cadre modélise les cas dans lesquels nous recherchons une petite structure combinatoire et nous pouvons nous permettre une durée d'exécution exponentielle par rapport à la taille de la solution / témoin .

Un problème avec un tel algorithme (par exemple, la couverture de vertex) est appelé FPT ( Fixed Parameter Tractable ).

La complexité paramétrée est une théorie mature, qui repose à la fois sur de solides fondements théoriques et sur des applications pratiques. Les problèmes de décision intéressants pour une telle théorie forment une hiérarchie très bien structurée de classes avec des problèmes naturels complets:

Bien sûr, elle est ouverte si l’une ou l’autre de ces inclusions est stricte ou non. Notez que si alors SAT a un algorithme sous-exponentiel (ce n'est pas trivial). La dernière déclaration relie la complexité prédéfinie avec l’ mentionné ci-dessus.E T $FPT=W[1]$$ETH$

Notez également que la recherche de tels effondrements n’est pas un exercice vide de choses: prouver que revient à prouver qu’il existe un algorithme modifiable à paramètre fixe pour la recherche de cliques.$W[1]=FPT$$k$