Czy istnieje twierdzenie Hierarchia czasu dla PH?

Czy to prawda, że w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie $O(n^k)$ (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w $O(n^{k-1})$ na żadnym poziomie hierarchia wielomianowa? Innymi słowy - czy istnieje twierdzenie o hierarchii czasu dla hierarchii wielomianowej, tak jak ma to miejsce w przypadku P i NP? Jeśli tak, odniesienie byłoby świetne.

Trudność, na jaką natrafiłem, polega na tym, że maszyna symulująca, gdy symuluje maszyny ze wszystkich poziomów hierarchii, nie znajduje się na żadnym odrębnym poziomie hierarchii. Co prowadzi do pokrewnego pytania - do jakiej najmniejszej klasy należy taka maszyna symulująca? Czy ma sens definiowanie klasy z alternatywami $O(n)$ (lub $O(\log n)$ / $O(\log \log n)$ )?

cc.complexity-theory reference-request polynomial-hierarchy time-hierarchy Joseph
źródło

Użycie liniowej liczby naprzemienności daje PSPACE, ponieważ formuła liczbowa Boolean jest kompletna z PSPACE.

Derrick Stolee,

Odpowiedzi:

Tak. Na przykład, zwykłe dowody twierdzenia o hierarchii czasu (poprzez bezpośrednią symulację dowolnych maszyn) można wykorzystać do wykazania, że dla każdego , nie jest podzbiorem . Powód zmiany z na $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Pi_c TIME[n^{k-1}]$ $\Sigma$ $\Pi$ polega na tym, że w tym argumencie przekątnym musimy zrobić „przeciwieństwo” maszyny, którą symulujemy, więc musimy działać w trybie uniwersalnym, gdy maszyna symulująca jest w trybie egzystencjalnym i odwrotnie.

Możesz także uzyskać taki wynik bez przełączania z na : dla każdego , nie jest podzbiorem . Można tego dokonać za pomocą dowodu na hierarchię czasu związaną z Zakiem (odniesienie: „ Hierarchia czasu maszyny Turinga ”, Theoretical Computer Science 26 (3): 327--333, 1983). Aby uzyskać wyraźne odniesienie do tej wersji twierdzenia o hierarchii czasu, zobacz Dieter van Melkebeek $\Sigma$ $\Pi$ $c \geq 1$ $\Sigma_c TIME[n^k]$ $\Sigma_c TIME[n^{k-1}]$ „ Badanie dolnych granic satysfakcji i powiązanych problemów ” (dostępne na jego stronie głównej).

Ryan Williams
źródło

Ta odpowiedź bardzo wyraźnie pokazuje istnienie twierdzenia o hierarchii czasu dla każdego odrębnego poziomu hierarchii. Nie oznacza to od razu istnienia takiego twierdzenia dla PH jako całości.

Joseph

Twoje mocniejsze pytanie będzie trudne do rozstrzygnięcia; to oznacza,

. Załóżmy, że istnieje

i język

, który jest w

do każdego

. Następnie

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

c

$c$

L

$L$

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

Σ_{d} T I M E [n^{k - 1}]

$\Sigma_d TIME[n^{k-1}]$

d

$d$

. To dlatego, że każdy język

jest

jakiegoś

w zależności od

(przez Savitch-twierdzenie typu argumentu). Więc jeśli

to w rzeczywistości każdy język w

L O G S P A C E \neq N P

$LOGSPACE \neq NP$

L \in L O G S P A C E

$L \in LOGSPACE$

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

L

$L$

L O G S P A C E = N P

$LOGSPACE = NP$

jest w

Σ_{c} T I M E [n^{k}]

$\Sigma_c TIME[n^k]$

dlaniektórych

, sprzecznych z tym, co chcesz pokazać.

Σ_{d} T I M E [n^{2}]

$\Sigma_d TIME[n^2]$

d

$d$

Ryan Williams

Odpowiedź na zmienione pytanie (wersja 4 pytania) brzmi: nie. Jeżeli problem decyzji L jest rozpuszczalny w czasie O ( n- ^k ) przez Σ _ı P urządzenia, a następnie L może być rozwiązany w czasie liniowo przez maszynę z Turingowi ORACLE L , który jest Σ _{i + 1} P urządzenia. Dlatego ∑ _i CZAS [O ( n ^k )] ⊆ Σ _{i +1} CZAS [O ( n )].

Tsuyoshi Ito
źródło

No, this is not how the definition of

Σ_{j} T I M E [t (n)]

$\Sigma_j TIME[t(n)]$ works. If

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for all

j, k

$j,k$ , then

N P \neq c o N P

$NP \neq coNP$ . If

N P = c o N P

$NP = coNP$ and

Σ_{j} T I M E [O (n^{k})] \subseteq Σ_{j + 1} T I M E [O (n)]

$\Sigma_j TIME[O(n^k)] \subseteq \Sigma_{j+1} TIME[O(n)]$ for every

j, k

$j,k$ , let

O (n^{c})

$O(n^c)$ be the running time of some nondeterministic algorithm for Tautology. Then we have

N T I M E [O (n^{c^{2}})] \subseteq Σ_{2} T I M E [O (n)] \subseteq N T I M E [O (n^{c})]

$NTIME[O(n^{c^2})] \subseteq \Sigma_{2} TIME[O(n)] \subseteq NTIME[O(n^{c})]$ , where the first inclusion is by assumption and the second inclusion follows from a standard simulation argument. This is a contradiction.

Ryan Williams

@Ryan: The definition I used is: L∈ΣiTIME[t(n)] iff there exist a language O∈Σ(i−1)P and a nondeterministic t(n)-time Turing machine with the oracle for O that recognizes L. I thought that this is the standard definition, but I do not have any reference to back up my claim. What is the definition you are using?

Tsuyoshi Ito

The definition is:

L \in Σ_{i} T I M E [t (n)]

$L \in \Sigma_i TIME[t(n)]$ iff there is a linear time predicate

R (x, y_{1}, \dots, y_{i})

$R(x,y_1,\ldots,y_i)$ such that

x \in L ⟺ (\exists y_{1} : | y_{1} | \leq t (| x |)) \dots (\forall y_{i} : | y_{i} | \leq t (| x |)) R (x, y_{1}, \dots, y_{i})

$x \in L \iff (\exists y_1 : |y_1|\leq t(|x|))\cdots (\forall y_i : |y_i| \leq t(|x|))R(x,y_1,\ldots,y_i)$ is true.

Ryan Williams

@Ryan: Ok, I did not know that definition. If that is what the asker wanted to ask, my answer does not apply.

Tsuyoshi Ito