Estou procurando referências sobre a complexidade do problema de balanceamento de fórmulas booleanas . Em particular,
- Sabia-se que as fórmulas booleanas podem ser balanceadas em ?
- Existe uma prova simples de que o balanceamento de fórmula booleana esteja em ?
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 .
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 (ou mesmo ou ). 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 .
Eu tenho uma prova para , no entanto, a prova não é simples e depende da prova de .
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] ).
Segue-se (surpreendentemente, pelo menos para mim) que o balanceamento de fórmulas booleanas ( ) também está em N C 1 :
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 é:
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 1
Questões
- Sabia-se que as fórmulas booleanas podem ser balanceadas em ( )? B F B ∈ A C 1
- Existe um argumento mais simples (por exemplo, não depender de ) para ? B F B ∈ A C 0
Respostas:
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.
fonte