Pytania otagowane jako hierarchy-theorems

2
Twierdzenie o hierarchii wielkości obwodu
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości f(n)f(n)f(n) i można ją obliczyć na podstawie obwodu …
3
Separacje klas złożoności bez twierdzeń hierarchicznych
Twierdzenia o hierarchii są podstawowymi narzędziami. Wiele z nich zebrano we wcześniejszym pytaniu (patrz Jakie hierarchie i / lub twierdzenia dotyczące hierarchii znasz? ). Niektóre separacje klas złożoności wynikają bezpośrednio z twierdzeń hierarchicznych. Przykłady takich dobrze znanych separacji: L ≠ PS.P.A C.miL≠PSPACEL\neq PSPACE , , , .N P ≠ N …
1
Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych?
Pytanie ogólne Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych? Oto kilka bardziej szczegółowych pytań: L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Czy dla wszystkich funkcji f (n) możliwych do zbudowania w przestrzeni f(n)f(n)f(n)jest DSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly ? Dla jakich funkcji h(n)h(n)h(n) wiadomo, że: dla wszystkich możliwych do zbudowania przestrzeni f(n)f(n)f(n) , …
1
Na
Wiemy to L⊆NL⊆P⊆NPL⊆NL⊆P⊆NP\mathcal{L}\subseteq \mathcal{N\!L}\subseteq\mathcal{P}\subseteq\mathcal{N\!P}. Z twierdzenia SavitchaNL⊆L2NL⊆L2\mathcal{N\!L}\subseteq\mathcal{L}^2, a od Space Hierarchy Teorem, L≠L2L≠L2\mathcal{L}\neq\mathcal{L}^2. Ponieważ nie wiemy, czyL≠PL≠P\mathcal L\neq\mathcal Pnie wiemy czy L2⊆PL2⊆P\mathcal L^2\subseteq\mathcal Pczy wiemy o tym L2⊈PL2⊈P\mathcal L^2\not\subseteq\mathcal P? Czy ktoś próbował udowodnić, że ? Jakie są najnowsze wyniki lub wysiłki w ten sposób? Próbowałem napisać ankietę na ten …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.