Limite inferior aprimorado na complexidade de circuitos monótonos de correspondência perfeita?

12

Razborov provou que todo circuito monótono que calcula a função de correspondência perfeita para gráficos bipartidos deve ter pelo menos portas (ele chamou de "permanente lógico"). Foi provado um limite inferior melhor para o mesmo problema desde então? (diga ?) Até onde me lembro, esse problema estava aberto em meados dos anos 90.nΩ(logn)2nϵ

Estou ciente de que a função de clique requer circuitos monotônicos de tamanho exponencial e assim por diante, mas estou interessado em uma correspondência perfeita especificamente.

Slimton
fonte

Respostas:

10

Eva Tardos provou que a lacuna é realmente exponencial, mostrando que existe uma função booleana monótona que possui circuitos poligonais, mas requer circuitos monotônicos de tamanho exponencial. Nada melhor do que o super polinômio é conhecido pela correspondência.

Raz tem como resultado que circuitos monótonos para correspondência têm profundidade linear. (Obrigado Klauck, por apontar o erro de digitação.)

AFAIK, não sabemos nada melhor.

Ref: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf

(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps

V Vinay
fonte
3
Vamos lá, é profundidade linear (e seu Raz e Wigderson).
Hartmut Klauck
4
N1/2NΩ(N)NΩ(registroN)