Bariery i złożoność obwodu monotonicznego

Dowody naturalne stanowią barierę dla udowodnienia niższych granic złożoności obwodu funkcji boolowskich. Nie bezpośrednio wynika, takiej bariery dla udowodnienia niższe granice na obwód złożoności. Czy jest jakiś postęp w identyfikowaniu takich barier? Czy istnieją inne bariery w ustawieniu monotonicznym?$monotone$

$\omega(n^k/(\log n)^k)$$O(n^k)$

$\omega(n^{k/4})$

Zatem bariera naturalnych dowodów nie wydaje się mieć zastosowania do złożoności obwodu monotonicznego.

Norbert Blum omówił, dlaczego dolne granice obwodów monotonicznych zasadniczo różnią się od obwodów z negacjami. Kluczową obserwacją Éva Tardos jest to, że niewielka modyfikacja funkcji Lovásza theta ma wykładniczą złożoność obwodu monotonicznego.

• Benjamin Rossman, Monotone Complexity of k-Clique on Random Graphs , FOCS 2010.
• Norbert Blum, On Negations in Boolean Networks , LNCS 5760 , 18–29, 2009.
• MI. Tardos, Różnica między złożonością obwodu monotonicznego i niemonotonicznego jest wykładnicza , Combinatorica 8 , 141–142, 1987. doi: 10.1007 / BF02122563

Punkt ma ogólną funkcję boolowską f, jest monotoniczna funkcja boolowska g, tak że dowolna superliniowa dolna granica g oznacza jedną na f. Lub silniejsza ogólna złożoność f jest równa monotonicznej złożoności od g do O (n).

Nadal nie jestem pewien, w jaki sposób odnosi się to do barier.