The Unit Gap: How Sharing Works in Boolean Circuits

O artigo demonstra que a diferença entre o tamanho mínimo de um circuito booleano e o de uma fórmula sobre a base AIG é sempre 0 ou 1, estabelecendo teoremas que definem quando o compartilhamento de portas é necessário e como essa lacuna unitária surge exclusivamente de um único gate com fan-out 2.

O essencial

Imagine que você precisa construir uma casa (uma função lógica) usando apenas dois tipos de blocos: blocos de "E" (AND) e a capacidade de inverter a cor de um bloco (NOT) de graça.

Neste mundo, existem duas formas de construir essa casa:

1. A Árvore (Fórmula): Você constrói uma estrutura onde cada bloco é usado apenas uma vez. Se você precisa usar um bloco em dois lugares diferentes, você é obrigado a construir duas cópias idênticas dele. É como ter que comprar dois tijolos iguais para fazer duas paredes, mesmo que você pudesse usar um só se pudesse "puxar" a parede de um lado para o outro.
2. O Circuito (DAG): Aqui, você pode fazer um "atalho". Se um bloco é útil em dois lugares, você constrói um só e divide o fio para ele ir para os dois lados. Isso é chamado de "compartilhamento".

O artigo de Kirill Krinkin investiga uma pergunta simples: Quanto de tamanho (quantos blocos) a gente economiza ao usar os atalhos do Circuito em vez da Árvore?

A resposta que ele encontrou é surpreendentemente simples e elegante.

A Grande Descoberta: A "Diferença de Um"

A maioria das pessoas esperaria que, para funções complexas, a Árvore fosse muito maior que o Circuito (talvez o dobro, o triplo, ou até exponencialmente maior).

Mas o autor descobriu que, neste sistema específico (onde inverter a cor é grátis), a economia é sempre exatamente 0 ou 1 bloco.

• Ou a Árvore e o Circuito têm o mesmo tamanho (diferença 0).
• Ou o Circuito é exatamente um bloco menor que a Árvore (diferença 1).

Nunca é 2, 3 ou 100 blocos. É sempre "nenhum" ou "um". O autor chama isso de Teorema da Lacuna Unitária.

Por que isso acontece? (A Analogia do "Bloco Mágico")

O segredo está em uma regra especial deste sistema: existe um bloco "1" (verdadeiro) que é grátis.
Imagine que você pode dizer: "Esta parede é feita de '1' E 'Minha Função'". Como o "1" é grátis, você não gasta nada para fazer essa conexão. Isso limita drasticamente o quanto a Árvore pode ser ineficiente. Ela nunca pode ficar "descontrolada".

Quando o Compartilhamento Acontece?

O autor descobriu regras muito claras sobre quando vale a pena fazer o "atalho" (compartilhar o bloco):

1. Regra do Tamanho Mínimo: Se a sua casa é pequena (usa 3 blocos ou menos), você nunca precisa de atalhos. A Árvore já é perfeita. O compartilhamento só começa a aparecer quando a casa precisa de 4 blocos ou mais.
2. Regra das Variáveis: Para que o compartilhamento valha a pena, a casa precisa ter pelo menos tantas "janelas" (variáveis de entrada) quanto o número total de blocos usados. Se você tem 5 variáveis, precisa de pelo menos 5 blocos para que o compartilhamento apareça.

Como funciona o "Atalho"? (Os Dois Mecanismos)

Quando o Circuito é 1 bloco menor que a Árvore, o autor provou que existe apenas uma única porta sendo compartilhada. E essa porta é compartilhada de apenas duas formas possíveis:

1. O Espelho (Dual-Polarity): Imagine que você tem um bloco que precisa ser usado em um lugar "normal" e em outro lugar "invertido" (como um espelho). Na Árvore, você teria que construir dois blocos (um normal, um invertido). No Circuito, você constrói um só e usa o fio normal em um lado e o fio invertido no outro. É como usar o mesmo espelho para ver o reflexo e o reflexo invertido.
2. O Repetidor (CSE - Mesma Polaridade): Imagine que você precisa usar o mesmo bloco duas vezes, exatamente da mesma forma, em dois lugares diferentes. Na Árvore, você constrói duas cópias. No Circuito, você constrói uma e divide o fio.

O autor provou que não existe nenhuma outra maneira de economizar exatamente 1 bloco. Se você tentar compartilhar mais de uma porta ou de outras formas, ou não economiza nada, ou o sistema não é o mais eficiente possível.

Resumo da Ópera

Pense na construção de circuitos lógicos como uma brincadeira de Lego onde:

• Você pode inverter a cor das peças de graça.
• Você tem uma peça "mágica" que custa zero.
• A pergunta é: "Quanto eu economizo se puder usar uma peça em dois lugares ao invés de comprar duas?"

A resposta deste artigo é: Você nunca economiza mais de uma peça.

• Se a estrutura for simples, você não economiza nada.
• Se for complexa o suficiente, você economiza exatamente uma peça, e só existe uma maneira específica de fazer isso (ou usando o espelho, ou dividindo o fio).

Isso é importante porque mostra que, mesmo em sistemas complexos, a "economia" de recursos tem uma estrutura muito rígida e previsível. Não é um caos; é uma regra de "tudo ou nada" (ou zero, ou um).

O autor também criou um "dicionário" de todas as casas possíveis até certo tamanho e mostrou que, em cerca de 85% dos casos, não há economia nenhuma. Mas nos 15% restantes, a economia é sempre exatamente de um bloco, seguindo um padrão perfeito.

Resumo técnico

Título: A Lacuna Unitária: Como o Compartilhamento Funciona em Circuitos Booleanos

Autor: Kirill Krinkin (Universidade Neapolis Pafos)
Base de Estudo: Gráficos AND-Inverter (AIG) com inversões gratuitas.

1. Problema e Motivação

O artigo investiga a diferença de tamanho (complexidade) entre o circuito booleano mínimo (um grafo acíclico dirigido - DAG, que permite reutilização de sinais) e a fórmula booleana mínima (um circuito em árvore, onde cada porta tem fan-out 1 e não permite reutilização).

• Contexto Geral: Em bases booleanas gerais, o tamanho da fórmula pode ser superpolinomialmente maior que o do circuito.
• Foco Específico: O autor foca na base AIG (And-Inverter Graph), que é a representação interna padrão em ferramentas modernas de síntese lógica (como o ABC). Nesta base:
  • As portas são apenas AND de duas entradas.
  • A inversão (NOT) é "gratuita" (um atributo da aresta, não uma porta).
  • O tamanho é medido pelo número de portas AND.
• Questão Central: Qual é a magnitude exata da economia obtida pelo compartilhamento (reconvergência) em circuitos ótimos AIG? O compartilhamento pode reduzir o tamanho arbitrariamente ou existe um limite estrutural?

2. Metodologia

O autor combina provas teóricas rigorosas com uma análise computacional extensa baseada em síntese exata.

• Síntese Baseada em SAT: Utilizou-se a abordagem de Kojevnikov et al. para codificar a existência de um AIG de tamanho $k$ como um problema de satisfatibilidade (SAT), permitindo a busca binária pelo tamanho ótimo $opt(f)$.
• Enumeração Completa e Amostragem:
  • n=3: Enumeração completa de todas as 256 funções.
  • n=4: Enumeração completa de todas as 65.536 funções.
  • n=5: Enumeração completa para $opt \le 4$; amostragem uniforme para $opt=5$.
  • n=6: Construção de circuitos específicos para verificar vocabulário de compartilhamento.
• Análise Estrutural: Uso de equivalência NPN (Negation, Permutation, Negation) para classificar funções e identificar padrões de compartilhamento.
• Interpretação Tropical: Reformulação dos resultados usando álgebra tropical (min-plus) para entender a recursão de árvores versus a correção de DAGs.

3. Principais Contribuições e Teoremas

O trabalho estabelece uma caracterização estrutural completa do compartilhamento em circuitos AIG ótimos.

A. Teorema da Lacuna Unitária (The Unit Gap Theorem)

• Enunciado: Para qualquer função booleana na base AIG com inversões gratuitas, a diferença entre o tamanho da fórmula e o tamanho do circuito é sempre 0 ou 1.
  $$gap(f) = tree(f) - opt(f) \in \{0, 1\}$$
• Implicação: Diferente de bases gerais onde a lacuna pode ser superpolinomial, na base AIG o compartilhamento oferece uma economia máxima de apenas uma porta AND. Isso ocorre devido à decomposição trivial $f = 1 \land f$ (onde 1 é gratuito) e à inversão gratuita.

B. Teorema do Limiar (Threshold Theorem)

• Enunciado: Se uma função $f$ possui $n$ variáveis essenciais e apresenta uma lacuna de 1 (ou seja, o circuito é estritamente menor que a árvore), então o tamanho do circuito ótimo deve satisfazer:
  $$opt(f) \ge n$$
• Significado: O compartilhamento só se torna necessário (e possível de economizar) quando o circuito é suficientemente complexo (pelo menos tão complexo quanto o número de variáveis). Para circuitos pequenos ($opt(f) \le 3$), o compartilhamento nunca é vantajoso.

C. Teorema da Árvore (Tree Theorem)

• Enunciado: Se $opt(f) \le 3$, então $gap(f) = 0$.
• Prova: Qualquer circuito reconvergente de 3 portas pode ser simplificado para uma árvore de tamanho $\le 2$. Portanto, para circuitos muito pequenos, a estrutura de árvore é sempre ótima.

D. Fórmula de Decomposição Exata

O artigo deriva uma fórmula recursiva para o tamanho do circuito ótimo:
$$opt(f) = 1 + opt(a) + opt(b) - s(a, b)$$
Onde $s(a, b) \in \{0, 1\}$ é um termo binário que conta o número de portas compartilhadas entre os sub-DAGs das entradas $a$ e $b$.

• Se $s=0$, o circuito é uma árvore.
• Se $s=1$, há exatamente uma porta compartilhada.

E. Teorema dos Dois Mecanismos (Two-Mechanism Theorem)

Quando $gap(f) = 1$, o compartilhamento ocorre através de exatamente uma porta com fan-out 2, utilizando um de dois mecanismos estruturais únicos:

1. Compartilhamento de Dupla Polaridade (Dual-polarity): A porta compartilhada é usada em polaridades opostas (uma entrada direta, outra invertida) pelos seus consumidores. Isso é comum em estruturas XOR ou MUX.
2. Compartilhamento de Subexpressão Comum (CSE - Same-polarity): A porta compartilhada é usada na mesma polaridade por ramos disjuntos. Este mecanismo só aparece para $n \ge 5$.

O artigo prova que nenhuma outra estrutura de compartilhamento pode produzir uma lacuna unitária.

4. Resultados Experimentais

• Distribuição da Lacuna:
  • Para $n=3$, 10,5% das funções têm $gap=1$.
  • Para $n=4$, 15,0% das funções têm $gap=1$.
  • Para $n=5$ (amostrado), 14,4% das funções têm $gap=1$.
  • A fração parece convergir para cerca de 15% (ou 85% das funções são árvores ótimas).
• Limiar de Ocorrência:
  • A lacuna 1 aparece pela primeira vez em $opt(f) = 4$ para $n=3,4$.
  • Para $n=5$, não existem funções de 5 variáveis com $gap=1$ em $opt=4$; elas aparecem apenas em $opt=5$.
• Tipos de Funções Gap-1:
  • Tipo A (Decomponível): Possuem uma decomposição AND não trivial que é uma árvore, mas o compartilhamento economiza 1 porta.
  • Tipo B (Incompatível com Árvore): Todas as decomposições de árvore não triviais custam $opt(f)+2$ ou mais. A única árvore possível custa $opt(f)+1$. Estas são tipicamente funções baseadas em XOR que exigem polaridades duplas.

5. Significado e Conclusão

• Natureza Atômica do Compartilhamento: O resultado mais profundo é que, na base AIG, o compartilhamento é "atômico". Em um circuito ótimo, a reconvergência (onde o DAG se desvia da árvore) ocorre em no máximo um ponto (uma única porta compartilhada). Não há estruturas complexas de compartilhamento múltiplo que reduzam o tamanho além de 1 porta.
• Limitações de Bases: O resultado é específico para AIG com inversões gratuitas e constante 1 gratuita. Em bases sem essas propriedades (ex: {AND, OR, NOT} com portas NOT explícitas), a lacuna pode ser maior.
• Implicações para Síntese Lógica: Para ferramentas de otimização de circuitos (como o ABC), isso sugere que buscas locais agressivas por compartilhamento múltiplo podem ter retornos decrescentes, pois a economia máxima é limitada a uma única porta por decomposição.
• Interpretação Tropical: O autor oferece uma visão elegante onde a complexidade da árvore é um "ponto fixo tropical" e a complexidade do circuito é uma "correção quantizada" de 0 ou 1 sobre esse ponto fixo.

Em resumo, o paper demonstra que, embora o compartilhamento seja fundamental para a complexidade de circuitos em geral, no contexto específico e prático dos AIGs modernos, seus benefícios são estritamente limitados e estruturalmente previsíveis: ou não há ganho, ou o ganho é exatamente de uma porta, obtido através de um dos dois mecanismos simples identificados.