Equilíbrio de fórmula booleana em

10

Estou procurando referências sobre a complexidade do problema de balanceamento de fórmulas booleanas . Em particular,

  1. Sabia-se que as fórmulas booleanas podem ser balanceadas em AC0 ?
  2. Existe uma prova simples de que o balanceamento de fórmula booleana esteja em AC0 ?

Por "simples", quero dizer uma prova mais simples do que a mencionada abaixo, em particular estou procurando uma prova que não dependa da avaliação da fórmula booleana em NC1 .


fundo

Aqui todas as classes de complexidade mencionadas são as uniformes.

BFB (Balanceamento de fórmula booleana):
Dada uma fórmula booleana φ ,
encontre uma fórmula booleana equilibrada equivalente.

Estou interessado na complexidade desse problema, em particular provas simples mostrando que o problema está em AC0 (ou mesmo TC0 ou NC1 ). Os argumentos comuns de balanceamento, como os baseados no lema de Spira, aplicam repetidas modificações estruturais na árvore de fórmulas, que parecem fornecer apenas BFBNC2 .

Eu tenho uma prova para BFBAC0 , no entanto, a prova não é simples e depende da prova de BFENC1 .

BFE (Boolean fórmula de avaliação)
Dada uma fórmula booleana e uma atribuição verdade τ para as variáveis em φ , Does τ satisfazer φ ( τ φ )?φτφ
τφτφ

É sabido pelo célebre resultado de Sam Buss que a avaliação da fórmula booleana ( ) pode ser calculada em N C 1 = A L o g T i m e (ver [Buss87] e [BCGR92] ).BFENC1=ALogTime

Segue-se (surpreendentemente, pelo menos para mim) que o balanceamento de fórmulas booleanas ( ) também está em N C 1 :BFBNC1

A idéia é que podemos codificar nas portas de entrada de B F E para obter uma fórmula equivalente a φ e essa é uma operação completamente sintática, computável em A C 0 . Como B F E possui fórmulas balanceadas, obtemos uma fórmula balanceada equivalente para φ . Em outras palavras, o algoritmo é:φBFEφAC0BFEφ

φλp.Eval(φ,p)

Motivação

Um argumento mais simples para o estar em (ou ou mesmo ) forneceria uma nova prova mais simples de pois é fácil ver que a versão balanceada do BFE pode ser resolvida em e podemos compor com e o resultado será em .A C 0 T C 0 N C 1 B F E N C 1 N C 1 B F B N C 1BFBAC0TC0NC1BFENC1NC1BFBNC1


Questões

  1. Sabia-se que as fórmulas booleanas podem ser balanceadas em ( )? B F B A C 1AC0BFBAC1
  2. Existe um argumento mais simples (por exemplo, não depender de ) para ? B F B A C 0BFENC1BFBAC0
Kaveh
fonte
3
Qual definição de "balance" você usa?
Dana Moshkovitz
11
@ Dana, podemos usar algo como (ou seja, com constantes específicas). Veja também o artigo de Bonnet e Buss, " Troca de tamanho e profundidade para fórmulas booleanas ", 2002.D e p t h = O ( lg S i z e )Depth<10lgSize+100Depth=O(lgSize)
Kaveh
concordou que a definição de "equilíbrio" deve ser esclarecida. isso é semelhante ao conceito de balanceamento em árvores binárias? por exemplo, "árvores auto balanceadas"
vzn 23/10/2013

Respostas:

3

Não tenho certeza se isso é muito relevante, mas em Algoritmos de espaço de log para caminhos e combinações em k-Trees (com base em uma longa história de trabalhos anteriores e especificamente em aulas de aritmetização em torno de NC1 e L por Limaye-Mahajan-Rao), mostramos como encontrar separadores balanceados recursivos para uma árvore no espaço de log. Esse limite pode muito bem ser improvável para se a árvore de entrada for fornecida diretamente na representação de string.NC1

A idéia básica é representar a árvore como uma expressão entre parênteses e encontrar separadores balanceados para elas. Observe que encontramos separadores de folhas, ou seja, subárvores com número equilibrado de folhas.

SamiD
fonte