Ilościowe formuły logiczne z logarytmicznymi przemianami

15

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:

(x1,x2,xa1)(xa1+1,xa2),(xalogn1,xalogn)F

Gdzie log n = N , a M jest wartością logiczną wzór zmiennych x 1 ... x n .alogn=nFx1xn

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

isaacg
źródło
3
Cóż, jest on gotowy do przemiennego czasu wielomianowego z logarytmicznie wieloma przemianami.
Emil Jeřábek wspiera Monikę
2
Uzgodnionym zapisem dla klasy złożoności tego problemu będzie STA ( ). Tutaj STA (s (n), t (n), a (n)) jest miarą przemienności czasoprzestrzennej wprowadzoną przez Bermana w „Złożoności teorii logicznych”, która pojawiła się w TCS w 1980 r. Klasa ta zawiera wszystkie decyzje problem rozstrzygalny przez naprzemienną maszynę Turinga w czasie t (n) z wykorzystaniem przestrzeni s (n) i naprzemiennie co najwyżej (n) razy w każdej gałęzi obliczeń. Jak zauważył Emil, twój problem powinien być kompletny dla tej klasy. ,nO(1),O(logn)
Christoph Haase
2
AltTime (lg n, poly (n))
Kaveh
Czy nie jest to również binarny analog klasy FOLL wprowadzonej przez Barringtona, Kadau, McKenzie i Lange. FOLL jest definiowany przez iterowanie bloku FO w zasadzie n-wejściowy, n-wyjściowy log logiczny obwodu AC0 n razy. Jest zbyt słaby, aby obliczyć parzystość, ale nie jest znany z tego, że należy do klasy mniejszej niż AC ^ 1. Potrafi robić wiele niebanalnych rzeczy, w tym zasilanie w grupie przemiennej przedstawionej jako tabliczka mnożenia. Chciałbym nazwać tę klasę PHL, ponieważ odpowiada to logowi iterowanemu log n razy. Myślę, że nadal nie jest jasne, czy można go porównać do PSPACE.
SamiD
Również jeśli grupa abelowa jest podawana przez obwód, który przyjmuje na wejściu dwie liczby n-bitowe i wysyła liczbę n-bitową, wówczas zasilanie jest w PHL przez dowód podobny do Barringtona i in. Powyżej.
SamiD

Odpowiedzi:

7

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

Ryan Williams
źródło
Bardzo dziękuję za komentarz i odpowiedź uzupełniającą. Zredagowałem swoją odpowiedź i dodałem szczegóły dotyczące uogólnienia argumentu. W rzeczywistości istnieje czas, przestrzeń i alternacja dla rodzajów obliczeń, które można zakodować.
Michael Wehar,
Dziękujemy za dodane odniesienie! Dodałem też bardziej zwięzłą odpowiedź, aby, miejmy nadzieję, wyjaśnić. Dzięki jeszcze raz. :)
Michael Wehar,
7

(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 znzmiennych, a następnie powtarza się przy każdej luce między konfiguracjami przy użyciu dla wszystkich kwantyfikatorów o z grubszalog(n)zmiennych.nlog2(n)log(n)

Rekurencja musi być kontynuowana do głębokości aby móc obliczyć długość 2log(n)gdzie każda konfiguracja ma najwyżejlog2(nn2log(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(nlog2(n)zmiennych.O(nlog3(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:

  • g(n)=n

  • c(n)=n2log2n

  • d(n)=2log2(n)

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 n2log2n bits of memory.

In other words, we have a better hardness result than before. In particular, the problem is hard for NTISP(2log2(n),n2log2n).

(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 n2log2n bits of memory.

In other words, the problem is hard for AltTimeSpace(log(n),2log32(n),n2log2n) 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. :)

Michael Wehar
źródło
1
Wouldn't the NL2-hardness follow straightaway from PH-hardness?
Nikhil
1
How exactly do we know point (1)? Don't we need 2k variables to get to some level k of PH? Maybe I'm missing a simple point here.
Markus
1
@MichaelWehar Sure, but we do know that NL2PH right? And that means every problem in NL2 reduces to QBF with constantly many alternations, which is a special case of log-many alternations?
Nikhil
1
@MichaelWehar Oops. Of course you're right! A related question here: cstheory.stackexchange.com/questions/14159/…
Nikhil
2
Why not NTISP(nlogn,poly(n))-hard?
Ryan Williams
1

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(2log2(n),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)log(n)

    2. t(n)2log2(n)

    3. s(n)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.

Michael Wehar
źródło
Also, there is another factor that I omitted. That is, the witness size used with each alternation takes up variables. In other words, the larger the witnesses, the fewer variables that we have meaning that potentially we can't represent as many bits per configuration causing us to possibly require there to be less space for the machine that we encode computations for.
Michael Wehar
Basically, all witness lengths for the quantifiers are sublinear and how large we can make them depends on the choice of a(n), t(n), and s(n).
Michael Wehar
Maybe an inner most there exists quantifier doesn't need to have restricted witness size because we can guess as we go.
Michael Wehar