Fórmulas booleanas quantificadas com alternâncias logarítmicas

15

Estou estudando um problema difícil para a classe de fórmulas booleanas quantificadas com um número logarítmico de alternâncias dos quantificadores. Um problema nesta classe seria semelhante a:

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

Onde alogn=n , e F é uma fórmula booleana das variáveis x1xn .

Esta classe contém claramente e está contido em uma P = P S P A C E . Existe um nome para esta classe? Existe algo mais conhecido sobre isso?PHAP=PSPACE

isaacg
fonte
3
Bem, está completo para alternar o tempo polinomial com muitas alternações logaritmicamente.
Emil Jeřábek apóia Monica 24/02
2
Uma notação acordada para a classe de complexidade desse problema seria STA ( ). Aqui, STA (s), t (n), a (n)) é a medida de alternância espaço-tempo introduzida por Berman em "A complexidade das teorias lógicas" que apareceu no TCS em 1980. Esta classe contém todas as decisões problema decidível por uma máquina de Turing alternada no tempo t (n) usando o espaço s (n) e alternando no máximo a (n) vezes em cada ramo da computação. Como Emil apontou, seu problema deve estar completo para esta aula. ,nO(1),O(logn)
Christoph Haase
2
AltTime (lg n, poly (n))
Kaveh
Não é também o análogo binário da classe FOLL introduzido por Barrington, Kadau, McKenzie e Lange. O FOLL é definido pela iteração de um bloco FO basicamente um log de circuito AC0 uniforme de n entradas e n saídas n vezes. É muito fraco para calcular Paridade, mas não se sabe que esteja contido em uma classe menor que AC ^ 1. Ele pode fazer várias coisas não triviais, incluindo ligar um grupo comutativo apresentado como uma tabela de multiplicação. Gostaria de chamar a classe em questão PHL porque corresponde a um log iterado do bloco PH n vezes. Acho que ainda não está claro se é comparável ao PSPACE.
SamiD 27/02
Além disso, se um grupo abeliano é dado por um circuito que recebe dois números de n bits e gera um número de n bits, a alimentação está em PHL por uma prova semelhante a Barrington et al.
SamiD 27/02

Respostas:

7

Com base na resposta de Michael Wehar, parece que pode facilmente mostrar que computações podem ser codificados em polysize tais QBFs: utiliza S ( log n ) alternâncias, cada um de p o l y ( n ) os bits, e fazer um argumento similar para o teorema de Savitch. Cada duas alternâncias vai dividir o tempo de execução do cálculo de um p o l y ( nNTISP(nlogn,poly(n))O(logn)poly(n) fator.poly(n)

Eu chamaria a classe , seguindo a notação das " trocas de tempo no espaço para a satisfação" de Fortnow, que também poderia ser citada para o argumento esboçado no parágrafo anterior (mas consulte o documento para referências anteriores).ΣO(logn)P

Ryan Williams
fonte
Muito obrigado pelo comentário e resposta de acompanhamento. Editei minha resposta e adicionei detalhes sobre a generalização do argumento. Na verdade, há uma troca de tempo, espaço e alternância para os tipos de cálculos que podem ser codificados.
25917 Michael Wehar
Obrigado pela referência adicionada! Além disso, adicionei uma resposta mais sucinta para esclarecer esperançosamente. Obrigado novamente. :)
Michael Wehar
7

(1) O que já sabemos:

Como você já declarou, o QBF com alternações de quantificadores é difícil para todos os níveis da hierarquia polinomial.log(n)

(2) Penso que também podemos provar o seguinte:

O problema é -Hard.NSPACE(log2(n))

(3) Aqui está minha justificativa informal para a afirmação anterior:

Dado um o espaço ligado MNT e uma cadeia de entrada, é preciso determinar se existe uma computação aceitar na dada cadeia de entrada.log2(n)

Cada configuração na computação pode ser representada por essencialmente bits. Em outras palavras, podemos representar uma configuração por um grupo de variáveis de log 2 ( n ) .log2(n)log2(n)

A idéia é que tenhamos uma configuração inicial e uma configuração final e precisamos adivinhar o cálculo que ocorre no meio. Nós adivinhamos recursivamente as configurações "intermediárias" usando quantificadores existentes e recorremos verificando se a configuração "esquerda" vai para o "meio" e a configuração "média" vai para a "direita" usando todos os quantificadores.

Agora, para fazer isso funcionar, em vez de escolher uma configuração "intermediária", precisamos escolher um grupo de configurações "intermediárias" igualmente espaçadas entre as configurações "esquerda" e "direita". Em particular, poderíamos adivinhar configurações "intermediárias" igualmente espaçadas, usando quantificadores existentes comnvariáveis ​​e, em seguida, recorra a cada intervalo entre configurações, usando para todos os quantificadores com aproximadamenteasvariáveislog(n).nlog2(n)log(n)

A recursão só precisa continuar até a profundidade para poder cobrir um cálculo do comprimento 2log(n)que cada configuração possui no máximolog2(n)muitos bits.n2log(n)=nlog(n)=2log2(n)log2(n)

Como a recursão é de profundidade , só temos O ( log ( n ) ) grupos de variáveis, ou seja, alternações. Como cada grupo de quantificadores possui apenas O(log(n))O(log(n))nlog2(n) variables, in total we have O(nlog3(n)) variables.

Feel free to offer any feedback or corrections. Thank you very much and I hope this helps a little bit.

(4) A more general assertion as suggested by Ryan's answer:

You should be able to carry out the preceding construction in a more general way. Consider the following:

At each step of the recursion, break up into g(n) groups of "intermediate" configurations using c(n) bits per configuration. Then, do the recursion to depth d(n).

As long as we don't have too many variables and too many alternations, this seems to work fine. Roughly, we need the following to be satisfied:

  • g(n)c(n)d(n)n
  • d(n)log(n)

Our generalized approach will be used to simulate non-deterministic Turing machines that run for g(n)d(n) steps using c(n) bits of memory.

In particular, we pick the following:

  • 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
fonte
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
Por que não 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
fonte
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