Meilleure complexité temporelle déterministe connue borne inférieure pour un problème naturel dans NP

Cette réponse aux problèmes majeurs non résolus en informatique théorique? question indique qu'il est ouvert si un problème particulier dans NP nécessite un temps .$\Omega(n^2)$

En regardant les commentaires sous la réponse, je me suis demandé:

Mis à part le rembourrage et les astuces similaires, quelle est la limite de temps la plus connue sur une machine RAM déterministe (ou une machine de Turing déterministe à plusieurs bandes) pour un problème intéressant dans NP (qui est indiqué de manière naturelle)?

Y a-t-il un problème naturel dans le NP qui est connu pour être insoluble en temps déterministe quadratique sur un modèle de machine raisonnable?

Essentiellement, ce que je recherche est un exemple qui exclut la revendication suivante:

tout problème de NP naturel peut être résolu en temps .$O(n^2)$

Connaissons-nous un problème NP similaire à ceux de l'article de Karp de 1972 ou de Garey et Johnson 1979 qui nécessite un temps déterministe ? Ou est-il possible, au meilleur de nos connaissances, que tous les problèmes naturels intéressants de NP puissent être résolus en temps déterministe O ( n 2 ) ?$\Omega(n^2)$$O(n^2)$

modifier

Clarification pour éliminer toute confusion résultant de l'inadéquation entre la borne inférieure et non la borne supérieure : je recherche un problème que nous savons que nous ne pouvons pas résoudre en . Si un problème satisfait à l'exigence plus forte que le temps Ω ( n 2 ) ou ω ( n 2 ) est nécessaire (pour toutes les entrées suffisamment grandes) alors mieux, mais infiniment souvent fera l'affaire.$o(n^2)$$\Omega(n^2)$$\omega(n^2)$

Adachi, Iwata et Kasai dans un article JACM 1984 montrent par réduction que le jeu Cat and -Mice a une limite inférieure de temps n Ω ( k ) . Le problème est en P pour chaque k . Le problème est joué sur un graphique dirigé. Les mouvements se composent du chat puis de l'une des k souris alternant les étapes. Les souris gagnent si elles peuvent atterrir sur un nœud de fromage désigné avant que le chat ne les touche. La question est de savoir si le chat a une victoire forcée. C'est en fait un problème complet, donc la borne inférieure est vraiment basée sur la diagonalisation qui donne la hiérarchie temporelle.$k$$n^{\Omega(k)}$$k$$k$

Grandjean a montré que la limite inférieure de temps de Pippenger, Paul, Szemeredi et Trotter s'applique à un codage SAT, bien que le résultat de Santhanam puisse le subsumer.

Outre les limites inférieures du compromis espace-temps pour SAT mentionnées dans d'autres commentaires, il existe un corpus de travaux sur les limites inférieures du programme de branchement qui impliquent des compromis espace-temps pour les machines de Turing. Pour les problèmes comme la FFT, le tri ou le calcul des fonctions de hachage universelles, il existe des limites inférieures de compromis quadratiques de Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari, mais ce sont des fonctions avec de nombreuses sorties. Pour les problèmes de décision dans P, il existe des limites inférieures de compromis espace-temps qui s'appliquent aux limites de temps qui sont mais celles-ci sont plus faibles que celles connues pour SAT.$O(n \log n)$

Le résultat classique que je connais est dû à Paul, Pippenger, Szemeredi et Trotter (1983) et sépare le temps linéaire déterministe du temps linéaire non déterministe.

Ensuite, il y a le résultat le plus récent de Fortnow, Lipton, van Melkebeek et Viglas (2004) qui a déjà été mentionné. L'unicité de ce résultat est qu'il s'agit d'un résultat de compromis temps-espace, englobant l'espace ainsi que le temps.

$\omega (n \sqrt{ \log ^{*} n} )$

$\mathbb{NP}$$O(n^{2})$

$\mathbb{P}$$\mathbb{NP}$$O(n^{2})$

$\mathbb{NP}$

1. $DTIME ( f(n) )$$f(n) = \Omega ( n^{2} \log n)$$\omega( n^{2} )$
2. $NTIME ( f(n) )$$f(n) = \omega ( n^{2} )$
3. $SPACE ( f(n) )$$f(n) = \omega ( n^{2} / \log n)$

Les limites inférieures ci-dessus devraient tenir pour la complexité en bits du problème.

$\mathbb{NP}$

Un exemple assez naturel vient peut -être de la complexité de Kolmogorov limitée dans le temps :

$k$$f(n) \leq n$$x$$M$$|M| < f(|x|)$$M$$x$$|x|^k$

Il s'agit simplement de reconsidérer la même question de P = NP d'une manière différente, si vous pouvez prouver que son insoluble en temps quadratique ou trouver une borne inférieure absolue, vous prouveriez P! = NP