Caracterização de fórmulas de leitura única na base binária completa

15

fundo

Uma fórmula de leitura única sobre um conjunto de portas (também chamada de base) é uma fórmula na qual cada variável de entrada aparece uma vez. As fórmulas de leitura única são comumente estudadas na base De Morgan (que possui as portas de 2 bits AND e OR e a porta de 1 bit NÃO) e na base binária completa (que possui todas as portas de 2 bits).

Assim, por exemplo, o AND de 2 bits pode ser escrito como uma fórmula de leitura única em qualquer base, mas a paridade de 2 bits não pode ser escrita como uma fórmula de leitura única na base de De Morgan.

O conjunto de todas as funções que podem ser escritas como uma fórmula de leitura única sobre a base de De Morgan tem uma caracterização combinatória. Ver, por exemplo, caracterização combinatória de fórmulas de leitura única por M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.

Questão

Existe uma caracterização alternativa do conjunto de funções que pode ser calculado por uma fórmula de leitura única na base binária completa?

Pergunta mais fácil (adicionada na v2)

Enquanto ainda estou interessado em uma resposta à pergunta original, como não recebi nenhuma resposta, pensei em fazer uma pergunta mais fácil: Quais são algumas técnicas de limite inferior que funcionam para fórmulas em toda a base binária? (Além dos listados abaixo.)

Observe que agora estou tentando diminuir o limite do tamanho da fórmula (= número de folhas). Para fórmulas de leitura única, temos o tamanho da fórmula = número de entradas. Portanto, se você puder provar que uma função precisa de uma fórmula de tamanho estritamente maior que n, isso também significa que ela não pode ser representada como uma fórmula de leitura única.

Estou ciente das seguintes técnicas (juntamente com uma referência para cada técnica da Complexidade da Função Booleana: Avanços e Fronteiras de Stasys Jukna ):

  • O método de Nechiporuk para funções universais (Seção 6.2): ​​Mostra um limite inferior de tamanho para uma determinada função. Isso não ajuda a encontrar limites inferiores para uma função específica em que você possa estar interessado.n2-o(1)
  • Teorema de Nechiporuk usando subfunções (Seção 6.5): Esta é uma técnica adequada de limite inferior no sentido de fornecer um limite inferior para qualquer função em que você esteja interessado. Por exemplo, mostra que qualquer fórmula sobre a base binária completa que representa o A função de distinção de elemento possui tamanho . (E esse é o maior limite inferior que a técnica pode provar - para qualquer função.)Ω(n2/registro⁡n)
cc.complexity-theory circuit-complexity lower-bounds formulas Robin Kothari
fonte
você olhou para BDDs, diagramas de decisão binária ? eles não estão bastante próximos em complexidade? mas, ainda não vi uma especificação ref sobre o assunto.
vzn

Respostas:

-2

existe também um método chamado limite inferior de Krapchenko "que pode ser um pouco maior que o método de Nechiporuks". veja John E Savage, Modelos de Computação, seção 9.4.2. (que é coberto logo após o método Nechiporuk na seção 9.4.1)

vzn
fonte
2
Obrigado pela referência, mas o método de Krapchenko funciona apenas com base em De Morgan (chamada de "base padrão" no livro de Savage). Minha pergunta é sobre a base binária completa.
Robin Kothari
se o método Nechiporuks funciona com base binária completa e o método é mostrado com base em De Morgan / padrão no livro Savages, por que a Krapchenkos também não trabalha com as duas? mas Savage concordou não tem um exemplo da base binária de Krapchenko / full.
vzn
1
A base binária completa é um superconjunto da base de De Morgan. Quaisquer limites inferiores que trabalhem contra a base binária completa também funcionam contra a base de De Morgan.
Robin Kothari
ok, tudo bem, o que exclui o método Krapchenko que trabalha com base binária completa? estou suspeitando que o método Nechiporuk provavelmente foi o primeiro aplicado à base de Morgan e depois estendido a toda a base, verdade? o que exclui o método Krapchenko?
vzn