Badam problem, który jest trudny dla klasy skwantyfikowanych formuł boolowskich z logarytmiczną liczbą zmian kwantyfikatorów. Problem w tej klasie wyglądałby następująco:
Gdzie log n = N , a M jest wartością logiczną wzór zmiennych x 1 ... x n .
Ta klasa zawiera wyraźnie i są zawarte w A P = P S . Czy istnieje nazwa dla tej klasy? Czy jest coś bardziej znanego na ten temat?
Odpowiedzi:
Opierając się na odpowiedzi Michaela Wehara, wydaje się, że możesz łatwo pokazać, że obliczenia można zakodować w polisize takich QBF: używasz alternatywnych O ( log n ) , każdy z p o l y ( n ) bitów i wykonaj argument podobny do twierdzenia Savitcha. Co dwie alternatywy podzielą czas wykonywania obliczeń przez p a l y ( nNTISP(nlogn,poly(n)) O(logn) poly(n) .poly(n)
Nazwałbym klasę , postępując zgodnie z zapisem w „Kompromisach czasowo-przestrzennych dla satysfakcji”, który można również zacytować dla argumentu nakreślonego w poprzednim akapicie (ale proszę zapoznać się z dokumentem dla wcześniejszych odniesień).ΣO(logn)P
źródło
(1) Co już wiemy:
Jak już wspomniano, QBF zlog(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 jestNSPACE(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:
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 roughly2log2(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 forNTISP(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 roughlylog(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 havelog(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 forAltTimeSpace(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. :)
źródło
A shorter answer.
See my longer answer for more details on the trade-offs betweena(n) , t(n) , and s(n) .
Note: In the above, when I say encode computations, I mean encode the computation without blowing up the instance size too much. That is, if we blow-up fromn size Turing machine input to poly(n) size formula, then I think that although the blow-up is polynomial, it is good to pay close attention to the degree of the polynomial. The reason for the semi-fine-grained perspective is to try and slightly better recognize how the different complexity measures a(n) , t(n) , and s(n) depend on each other.
źródło