(1) Co już wiemy:
Jak już wspomniano, QBF z log(n) naprzemiennych kwantyfikatorów jest trudne dla każdego poziomu hierarchii wielomianowej.
(2) Myślę, że możemy również udowodnić, co następuje:
Problemem jest NSPACE(log2(n)) -hard.
(3) Oto moje nieformalne uzasadnienie powyższego stwierdzenia:
Biorąc pod uwagę log2(n) miejsca związanego NTM i wejściowy łańcuch znaków, musimy stwierdzić, czy istnieje przyjmującą obliczeń na dany ciąg wejściowych.
Każda konfiguracja w obliczeniach może być reprezentowana przez bitów. Innymi słowy, możemy przedstawić konfigurację przez grupę log 2 ( n )log2(n)log2(n) zmiennych .
Chodzi o to, że mamy konfigurację początkową i konfigurację końcową i musimy odgadnąć obliczenia występujące pomiędzy nimi. Rekurencyjnie odgadujemy konfiguracje „środkowe” przy użyciu istniejących kwantyfikatorów i powtarzamy, sprawdzając, czy konfiguracja „lewa” idzie do „środkowej”, a konfiguracja „środkowa” - do „prawej”, używając dla wszystkich kwantyfikatorów.
Teraz, aby to zadziałało, zamiast wybierać jedną konfigurację „środkową”, musimy wybrać grupę równomiernie rozmieszczonych konfiguracji „pośrednich” między konfiguracjami „lewą” i „prawą”. W szczególności możemy zgadywać równomiernie rozmieszczonych konfiguracji „pośrednich” z wykorzystaniem istniejących kwantyfikatorów zn−−√zmiennych, a następnie powtarza się przy każdej luce między konfiguracjami przy użyciu dla wszystkich kwantyfikatorów o z grubszalog(n)zmiennych.n−−√∗log2(n)log(n)
Rekurencja musi być kontynuowana do głębokości aby móc obliczyć długość √2∗log(n)gdzie każda konfiguracja ma najwyżejlog2(nn−−√2∗log(n)=nlog(n)=2log2(n)log2(n) wielu bitów.
Ponieważ rekurencja ma głębokość , mamy tylko grupy zmiennych O ( log ( n ) ) , tj. Przemienności. Ponieważ każda grupa kwantyfikatorów ma tylko √O(log(n))O(log(n))zmiennych, w sumie mamyO( √n−−√∗log2(n)zmiennych.O(n−−√∗log3(n))
Zachęcamy do zgłaszania wszelkich uwag i poprawek. Dziękuję bardzo i mam nadzieję, że to trochę pomoże.
(4) Bardziej ogólne stwierdzenie, jak sugeruje odpowiedź Ryana:
Powinieneś być w stanie przeprowadzić poprzednią budowę w bardziej ogólny sposób. Rozważ następujące:
Na każdym etapie rekurencji podziel na grupy konfiguracji „pośrednich” przy użyciu c ( n ) bitów na konfigurację. Następnie wykonaj rekurencję na głębokość d ( n )g(n)c(n)d(n) .
Dopóki nie mamy zbyt wielu zmiennych i zbyt wielu alternatyw, wydaje się, że działa dobrze. Z grubsza potrzebujemy:
- g(n)∗c(n)∗d(n)≤n
- d(n)≤log(n)
g(n)d(n)c(n) bitów pamięci.
W szczególności wybieramy:
The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly 2log2(n) steps using n√2∗log2n bits of memory.
In other words, we have a better hardness result than before. In particular, the problem is hard for NTISP(2log2(n),n√2∗log2n).
(5) Further generalizations:
In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines. However, we may be able to simulate alternating time and space bounded Turing machines as well.
Let me explain a little bit. So we use roughly log(n) alternations to do the recursion to depth log(n). However, we could use some of the alternations initially, let's say log(n)−−−−−√. Then, we could use the remaining log(n)−−−−−√ alternations to go to depth log(n)−−−−−√.
In this case, we could simulate alternating Turing machines that have log(n)−−−−−√ alternations with sublinear witness lengths, run for 2log32(n) steps, and use n√2∗log2n bits of memory.
In other words, the problem is hard for AltTimeSpace(log(n)−−−−−√,2log32(n),n√2∗log2n) with sublinear witness lengths. Alternatively, this class could be written using the STA notation mentioned in the comments above.
Thank you for the comments and feel free to offer any further corrections or clarifications. :)