Séparation de l'espace journal du temps polynomial

Il est clair que tout problème décidable dans un espace de log déterministe ( $L$ ) s'exécute au maximum dans le temps polynomial ( $P$ ). Il y a une multitude de classes de complexité entre $L$ et $P$ . Les exemples incluent $NL$ , $LogCFL$ , $NC^i$ , $SAC^i$ , $AC^i$ , $SC^i$ . On croit généralement que $L \neq P$ .

Dans l' un de mes messages de blog je l' ai mentionné deux approches (ainsi que les correspondants conjectures) vers prouver $L \neq P$ . Ces deux approches sont basées sur des programmes de branchement et sont espacées de 20 ans !! Existe-t-il d'autres approches et / ou conjectures pour séparer $L$ de $P$ (ou) séparant les classes intermédiaires entre $L$ et $P$ ?

Profondeur circuit des bornes inférieures ( de manière équivalente, des limites de taille de formule inférieure) sont probablement l'approche la plus naturelle: Un Super- $\log^2(n)$ limite inférieure profondeur d'un problème dans $\mathsf P$ séparerait $\mathsf P$ de $\mathsf L$ , et la technique de la complexité de la communication Karchmer-Wigderson peut être le naturel pour ça.

[1] prouve une borne inférieure pour les instances de mincost-flow dont la taille des bits est suffisamment grande (mais toujours linéaire) par rapport à la taille du graphique, et a en outre prouvé que si l'on pouvait montrer la même borne inférieure pour les entrées de suffisamment petites la taille en bits impliquerait (et donc P ≠ L ). C'est, à un niveau élevé, la même chose que la réponse de Noam en ce sens qu'il s'agit de prouver les limites inférieures de la profondeur du circuit (= les limites inférieures de la formule), mais semble être une direction très différente de celle des jeux de Karchmer-Wigderson.$\mathsf{P} \neq \mathsf{NC}$$\mathsf{P} \neq \mathsf{L}$

Plus en détail, [1] montre ce qui suit. En utilisant la même notation que dans l'article, laissez désigner le langage de flux mincost. Nous pouvons considérer le langage de flux mincost sur les graphes à n- sommets, noté L ( n ) , comme un sous-ensemble de Z k ( n ) pour certains k ( n ) = Θ ( n 2 ) , avec des entiers codés par des chaînes de bits . Soit B ( a , n ) l'ensemble de tous les vecteurs dans Z k ( n $L$$n$$L(n)$$\mathbb{Z}^{k(n)}$$k(n) = \Theta(n^2)$$B(a,n)$$\mathbb{Z}^{k(n)}$où chaque coordonnée entière a une taille de bit au plus . Étant donné une fonction f ( x 1 , … , x k ) (nous préciserons quel type de fonction plus tard), nous disons que f sépare L ( n ) dans B ( a , n ) si les points dans L ( n ) ∩ B ( a , n ) sont exactement ceux → x ∈ B ( a $an$$f(x_1, \dotsc, x_k)$$f$$L(n)$$B(a,n)$$L(n) \cap B(a,n)$ tel que f ( → x ) = 1 .$\vec{x} \in B(a,n)$$f(\vec{x}) = 1$

$L(n)$$B(a,n)$M ≤ 2 n / d x 1 , … , x k a < 1 / ( 2 d ) P ≠ N $\det(M(\vec{x}))$$M$$\leq 2^{n/d}$$x_1, \dotsc, x_k$$a < 1/(2d)$$\mathsf{P} \neq \mathsf{NC}$

La relation entre le bit lié et la taille liée est ici cruciale. Dans le même article, il a montré:2 n /$an$$2^{n/d}$

Théorème [1, Théorème 7.4] L'hypothèse de la proposition précédente est valable pour toutes les bornes binaires suffisamment grandes .$a$

La preuve du théorème ci-dessus utilise quelques marteaux lourds comme boîtes noires, mais est par ailleurs élémentaire (note: "élémentaire" " facile "). À savoir, il utilise la borne de Milnor-Thom sur le nombre de composants connectés d'une variété semi-algébrique réelle (la même borne utilisée par Ben-Or pour prouver les bornes inférieures sur la distinction / tri des éléments dans le modèle d'arbre de calcul réel), la décomposition de Collins ( utilisé pour prouver l'élimination efficace des quantificateurs sur ), un argument de position général et quelques autres idées. Cependant, toutes ces techniques ne dépendaient que du degré des polynômes impliqués, et ne peuvent donc pas être utilisées pour prouver comme dans la proposition ci-dessus (en effet, [1, Prop. 7.5] construit un polynômeR P ≠ N C g dét g $\neq$$\mathbb{R}$$\mathsf{P} \neq \mathsf{NC}$$g$ du même degré que tel que la proposition ci-dessus échoue avec à la place de ). Analyser cette situation et rechercher des propriétés dépassant le degré a été l'une des inspirations du GCT.$\det$$g$$\det$

[1] K. Mulmuley. Limites inférieures dans un modèle parallèle sans opérations sur les bits . SIAM J. Comput., 28 (4), 1460-1509, 1999

Cela a fait ma journée quand mon ami James m'a dit que ce fil d'il y a longtemps avait été ravivé. Merci pour ça.

De plus, j'avais envie de partager quelques références intéressantes concernant L vs Log (DCFL) vs Log (CFL). Passez une bonne journée!

http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1

http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true

http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1

http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata

ce nouveau document vient d'être souligné par Luca Aceto dans son blog comme un meilleur article étudiant EATCS à ICALP 2014 et a une nouvelle façon de séparer NL / P:

• Résultats de dureté pour Wehar de non-vide d' intersection

  Nous réexaminons soigneusement une construction de Karakostas, Lipton et Viglas (2003) pour montrer que le problème de non-vide d'intersection pour les DFA (automates finis déterministes) caractérise la classe de complexité NL. En particulier, s'il est limité à un alphabet de bande de travail binaire, il existe des constantes et telles que pour chaque intersection non-vacuité pour DFA est résoluble dans l' espace , mais ne peut pas être résolue dans espace . Nous optimisons la construction pour montrer qu'un nombre arbitraire de non-vide d'intersection de DFA n'est pas résoluble dansc 2 k k c 1 k log ( n ) c 2 k log ( n ) o ( $c_1$$c_2$$k$$k$$c_1 k \log(n)$$c_2 k \log(n)$f(k)=o(k)kknf(k)ckkn$o \left( \frac{n}{\log(n) \log(\log(n))} \right)$espace. De plus, s'il existe une fonction telle que pour chaque intersection la non-vacuité pour DFA est résoluble en temps, alors P ≠ NL. S'il n'existe pas de constante telle que pour chaque intersection la non-vacuité pour DFA soit résoluble en temps, alors P ne contient aucune classe de complexité d'espace supérieure à NL.$f(k) = o(k)$$k$$k$$n^{f(k)}$$c$$k$$k$$n^c$