Hambatan dan Kompleksitas Sirkuit Monoton

$monotone$

Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE. In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in 1987: $\omega(n^k/(\log n)^k)$, versus batas atas kekuatan kasar $O(n^k)$.

Rossman menunjukkan batas bawah $\omega(n^{k/4})$untuk kompleksitas kasus rata-rata dalam model grafik acak Erdő-Rényi; Amano sebelumnya menunjukkan ini pada dasarnya juga merupakan batas atas. Lemma semi-bunga matahari yang membentuk bagian penting dari kertas ini agak rapi.

Jadi penghalang bukti alami tampaknya tidak berlaku untuk kompleksitas sirkuit monoton.

Norbert Blum telah membahas mengapa batas bawah untuk sirkuit monoton pada dasarnya berbeda dari sirkuit dengan negasi. Pengamatan utama Éva Tardos adalah bahwa modifikasi kecil fungsi Lovász theta memiliki kompleksitas sirkuit monoton eksponensial.

• Benjamin Rossman, Kompleksitas Monoton k-Clique pada Grafik Acak , FOCS 2010.
• Norbert Blum, Tentang Negasi dalam Boolean Networks , LNCS 5760 , 18-29, 2009.
• É. Tardos, Celah Antara Kompleksitas Monoton dan Sirkuit Non-Monoton adalah Eksponensial , Combinatorica 8 , 141–142, 1987. doi: 10.1007 / BF02122563

Titik diberikan fungsi boolean umum f ada fungsi boolean monoton g sehingga setiap superliner yang lebih rendah terikat pada g menyiratkan satu pada f. Atau lebih kuat, kompleksitas umum f sama dengan kompleksitas monoton g hingga O (n).

Saya masih tidak yakin bagaimana ini berhubungan dengan hambatan.