L / P / PSpace vs P / NP

en 1979 Hopcroft / Ullman a écrit que L ⊆ P ⊆ NP ⊆ PSpace est connu mais L ⊊ PSpace est le seul confinement approprié (et trivial) connu bien que tous soient supposés être des confinements appropriés, et "où les choses se tiennent encore" ~ 4 décennies plus tard .

depuis lors, existe-t-il des liens connus entre L ⊊ P, P ⊊ PSpace et P ⊊ NP? sont-ils tous toujours considérés comme indépendants, ou y a-t-il des signes d'une certaine interdépendance?

motivation: cette question est en partie inspirée par les résultats récents de Backurs-Indyk liant SETH à O (n ² ) distance d'édition. SETH est le temps exponentiel et la distance d'édition est PTime. (& aussi un peu la question de prouver les bornes inférieures en prouvant les bornes supérieures )

cc.complexity-theory reference-request lower-bounds p-vs-np conditional-results vzn
la source

Réponses:

Le seul confinement approprié connu est toujours , bien que l'on pense généralement qu'ils sont différents. Tous les autres sont encore ouverts. $L \subsetneq PSPACE$

$P\neq NP$ $P \neq NP$ $2^n$ $2^{n/k}$ $P$ $\Omega(n^k)$ $2^{n}$ $2^{(1-\delta)n}$

$O^\star(2^n)$ $2^{n}poly(n^k)/n^{\omega(1)}$ $n^k$ $NEXP \not \subseteq P/poly$

palindrome
la source

Comment cela répond-il à la question, qui pose des questions sur les implications (ou "interdépendances", quoi que cela puisse signifier) entre trois déclarations?

András Salamon

Je visais à répondre à la question sur la base de sa motivation déclarée. Je ne suis personnellement au courant d'aucune "interdépendance" non triviale entre les déclarations.

palindrome