Ilościowe formuły logiczne z logarytmicznymi przemianami

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:

$\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F$

Gdzie log n = N , a M jest wartością logiczną wzór zmiennych x 1 ... x n .$a_{\log n} = n$$F$$x_1 \ldots x_n$

Ta klasa zawiera wyraźnie i są zawarte w A P = P $PH$ . Czy istnieje nazwa dla tej klasy? Czy jest coś bardziej znanego na ten temat?$AP = PSPACE$

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 ( $NTISP(n^{\log n},poly(n))$$O(\log n)$$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ń).$\Sigma_{O(\log n)} P$

(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(log^2(n))$ -hard.

(3) Oto moje nieformalne uzasadnienie powyższego stwierdzenia:

Biorąc pod uwagę $log^2(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 $\log^2(n)$$\log^2(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 z$\sqrt{n}$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.$\sqrt{n} * log^2(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($\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$$\log^2(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($\sqrt{n} * log^2(n)$zmiennych.$O(\sqrt{n} * log^3(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) \leq n$
• $d(n) \leq \log(n)$

$g(n)^{d(n)}$$c(n)$ bitów pamięci.

W szczególności wybieramy:

• $g(n) = \sqrt{n}$

• $c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$

• $d(n) = 2 * \log^2(n)$

The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, we have a better hardness result than before. In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$.

(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 $\sqrt{\log(n)}$. Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ 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. :)

A shorter answer.

Initial observations:

• The problem is hard for every level of the polynomial hierarchy.
• The problem is hard for alternating Turing machines with $\log(n)$ alternations that run for polynomial time.

Deeper Insights:

• Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ Turing machines.
• Also, as Ryan pointed out, the problem can encode computations for $NTimeSpace(2^{\log^2(n)}, \sqrt{n})$ Turing machines.

• More generally, the problem can encode computations for machines corresponding to various classes of the form $AltTimeSpace(a(n), t(n), s(n))$ with restricted witness lengths. I'm not quite sure what the exact relationship between $a(n)$, $t(n)$, and $s(n)$ has to be, but we know that:

  1. $\; \; a(n) \leq \log(n)$

  2. $\; \; t(n) \leq 2^{\log^2(n)}$

  3. $\; \; s(n) \leq n$

See my longer answer for more details on the trade-offs between $a(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 from $n$ 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.