Pytania oznaczone «separation»

Wyraźny rozdział między konstruowaniem w czasie a konstruowaniem w przestrzeni?

Pokaż funkcję którą można konstruować w przestrzeni, ale nie można jej konstruować w czasie.f(n)fa(n)f(n) Czy ten problem jest związany z możliwym rozdzieleniem klas złożoności DTIME (f (n)) i SPACJA (f

Czy można zastosować opisową złożoną wersję twierdzenia Rice'a do oddzielenia AC0 i PSPACE?

W tym pytaniu wspomniano, że istnieją opisowe wersje złożoności twierdzenia Rice'a. Znalazłem dowód na następujące twierdzenie: Biorąc pod uwagę klasę złożoności C , nietrywialnych właściwości języków w C nie można obliczyć w C Wcześniej opublikowałem znaleziony dowód, ale ponieważ był on tak...