Fórmula booleana equilibrada en

10

Estoy buscando referencias sobre la complejidad del problema de equilibrio de la fórmula booleana . En particular,

  1. ¿Se sabía que las fórmulas booleanas se pueden equilibrar en ?AC0
  2. ¿Hay alguna prueba simple de que el equilibrio de la fórmula booleana esté en ?AC0

Por "simple" me refiero a una prueba más simple que la que menciono a continuación, en particular, estoy buscando una prueba que no dependa de que la evaluación de la fórmula booleana esté en .NC1


Antecedentes

Aquí todas las clases de complejidad mencionadas son las uniformes.

BFB (equilibrio de la fórmula booleana):
dada una fórmula booleana , encuentre una fórmula booleana equilibrada equivalente.φ

Estoy interesado en la complejidad de este problema, en particular las pruebas simples que muestran que el problema está en (o incluso T C 0 o N C 1 ). Los argumentos de equilibrio comunes como los basados ​​en el lema de Spira aplican modificaciones estructurales repetidas al árbol de fórmulas que parecen dar solo B F B N C 2 .AC0TC0NC1BFBNC2

Tengo una prueba para , sin embargo, la prueba no es simple y depende de la prueba de B F E N C 1 .BFBAC0BFENC1


φτφ
τφτφ

BFENC1=ALogTime

BFBNC1

φBFEφAC0BFEφ

φλp.Eval(φ,p)

Motivación

Un argumento más simple para que esté en (o o incluso ) daría una nueva prueba más simple de ya que es fácil ver que la versión balanceada de BFE se puede resolver en y podemos componerla con y el resultado estará en .BFBAC0TC0NC1BFENC1NC1BFBNC1


Preguntas

  1. ¿Se sabía que las fórmulas booleanas se pueden equilibrar en ( )?AC0BFBAC1
  2. ¿Existe un argumento más simple (por ejemplo, no confiar en ) para ?BFENC1BFBAC0
Kaveh
fuente
3
¿Qué definición de "equilibrio" utiliza?
Dana Moshkovitz
1
@Dana, podemos usar algo como (es decir, con constantes específicas). Véase también el documento de Bonnet and Buss " Tamaño-Profundidad de compensación para fórmulas booleanas ", 2002.Depth<10lgSize+100Depth=O(lgSize)
Kaveh
acordó que la definición de "equilibrio" debería quedar clara. ¿Es esto similar al concepto de equilibrio en árboles binarios? por ejemplo, "árboles auto equilibrados"
vzn

Respuestas:

3

No estoy seguro de si esto es muy relevante, pero en Algoritmos de espacio de registro para rutas y coincidencias en k-Trees (basándose en una larga historia de trabajo pasado y específicamente en clases de Aritmetización alrededor de NC1 y L por Limaye-Mahajan-Rao) mostramos cómo encontrar separadores balanceados recursivos para un árbol en Logspace. Este límite puede muy bien mejorarse a si el árbol de entrada se da directamente en la representación de cadena.NC1

La idea básica es representar el árbol como una expresión de paréntesis y encontrar separadores equilibrados para estos. Observe que encontramos separadores de hojas, es decir, subárboles que están equilibrados con el número de hojas.

SamiD
fuente