Peningkatan batas bawah pada kompleksitas sirkuit monoton pencocokan sempurna?

Razborov membuktikan bahwa setiap rangkaian monoton yang menghitung fungsi pencocokan sempurna untuk grafik bipartit harus memiliki setidaknya gerbang (ia menyebutnya "permanen logis"). Apakah batas bawah yang lebih baik untuk masalah yang sama telah terbukti sejak saat itu? (katakanlah ?) Sejauh yang saya ingat masalah ini terbuka pada pertengahan 1990-an. $n^{\Omega(\log n)}$ $2^{n^\epsilon}$

Saya sadar bahwa fungsi klik membutuhkan sirkuit monoton ukuran eksponensial dan sebagainya, tetapi saya tertarik pada pencocokan sempurna secara khusus.

cc.complexity-theory circuit-complexity matching Slimton
sumber

Jawaban:

Eva Tardos membuktikan bahwa celah tersebut benar-benar eksponensial dengan menunjukkan bahwa ada fungsi boolean monoton yang memiliki sirkuit ukuran poli tetapi membutuhkan sirkuit monoton ukuran eksponensial. Tidak ada yang lebih baik daripada super polinomial yang diketahui cocok.

Raz memiliki hasil bahwa rangkaian monoton untuk pencocokan memiliki kedalaman linier. (Terima kasih Klauck, karena menunjuk kesalahan ketik.)

AFAIK, kami tidak tahu yang lebih baik.

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

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

V Vinay
sumber

Ayo, ini kedalaman linear (dan Raz dan Wigderson).

Hartmut Klauck

N^{1 / 2}

$N^{1/2}$

N

$N$

Ω (N)

$\Omega(N)$

N^{Ω (\log N)}

$N^{\Omega(\log N)}$