UM PROBLEMA EXTREMAL SOBRE O HIPERCUBO E APLICAÇÕES A CIRCUITOS ASSÍNCRONOS

CARLOS GUSTAVO TAMM DE ARAUJO MOREIRA (IMPA) PABLO EMANUEL (IMPA E PUC)

Investigamos o seguinte problema combinatório extremal, motivado por um problema sobre circuitos assíncronos: estime o menor valor possível de B = B(n) para que exista uma função

F : {0, 1}^{B} → n

tal que:

(i) Para quaisquer x < n, y < n, existem m, n em {0, 1}^{B} com F (m) = x, F (n) = y, e dist(m, n) = 1, ou seja, m e n diferem em apenas um bit.

(ii) Para qualquer x < n, a imagem inversa de x por F é conexa, i.e., dados m, n com F (m) = F (n) = x, existem m = l(0), …, l(k) = n com dist(l(i), l(i + 1)) = 1 e F (l(i)) = x, para 0 ≤ i < l.

Provamos que

2 log_{2} n − log_{2} log_{2} n − 1 < B(n) < 2 log_{2} n − log_{2} log_{2} n + 2

para todo n natural. A estimativa superior anterior era 2 log_{2} n − 1. Descreveremos brevemente o problema computacional que motiva este problema combinatório.