Złożoność obliczeniowa a hierarchia Chomsky'ego

Zastanawiam się ogólnie nad związkiem między złożonością obliczeniową a hierarchią Chomsky'ego.

W szczególności, jeśli wiem, że jakiś problem jest NP-zupełny, czy wynika z tego, że język tego problemu nie jest pozbawiony kontekstu?

Na przykład problem kliki jest NP-zupełny. Czy wynika z tego, że język odpowiadający modelom z klikami ma pewną minimalną złożoność w hierarchii Chomsky'ego (dla wszystkich / niektórych sposobów kodowania modeli jako ciągów?)

complexity-theory formal-languages

— sjmc
źródło

istnieje wiele subtelnych powiązań, ale są to głównie pojęcia ortogonalne. zasadniczo różne problemy dotyczące każdej klasy językowej mogą mieć różne złożoności. jak dla NP kompletności jest twierdzenie o „języków rzadkich” ....

— vzn

W hierarchii Chomsky'ego istnieją cztery klasy języka:

$\mathrm{TIME}(n)$ $\mathrm{TIME}(o(n\log n))$ $\mathrm{SPACE}(0)$ $\mathrm{SPACE}(o(\log\log n))$
$\mathrm{LOGCFL}$ $\mathrm{LOGCFL}$ $\mathrm{AC}^1$ $\mathrm{P}$
$\mathrm{NSPACE}(n)$
Nieograniczone gramatyki - klasa ta obejmuje wszystkie rekurencyjnie wymienialne języki.

$\neq$

— Yuval Filmus
źródło

Istnieje wiele nieregularnych języków czasu liniowego. Prawdopodobnie chodziło o SPACJĘ (0) lub SPACJĘ (o (log log n)).

— Emil Jeřábek 3.0

T I M E (f (n))

$\mathrm{TIME}(f(n))$