Jaka jest minimalna wielkość obwodu, który oblicza PARYSTOŚĆ?

Jest to klasyczny wynik, że każdy obwód wachlarza 2 AND-OR-NOT, który oblicza PARITY ze zmiennych wejściowych, ma rozmiar co najmniej i jest ostry. (Definiujemy rozmiar jako liczbę bramek AND i OR). Dowodem jest eliminacja bramki i wydaje się, że zawodzi, jeśli pozwolimy na dowolne wbicie. Co jest znane w tej sprawie?$3(n-1)$

W szczególności, czy ktoś zna przykład, kiedy pomaga większy wachlarz, tzn. Potrzebujemy mniej niż bramek?$3(n-1)$

Aktualizacja 18 października. Marzio wykazał, że dla wystarcza nawet bramek przy użyciu formy PARYSTYCZNEJ CNF. Oznacza to ograniczenie dla ogólnego . Czy TY możesz zrobić lepiej?5 ⌊ $n=3$$5$$\lfloor \frac 52 n \rfloor-2$$n$

Możliwe jest obliczenie parzystości przy użyciu jedynie bramek 2,33n + C. Konstrukcja jest dość prosta i jest podana w tym artykule.

http://link.springer.com/article/10.3103/S0027132215050083

Oto przykład obwodu dla parzystości 6 zmiennych przy użyciu tylko 12 bramek (każda bramka jest bramką AND, okrąg w pobliżu wejścia bramki oznacza, że ​​wejście to jest odwrócone). Zauważ, że obwód dla parzystości 6 zmiennych, który jest konstruowany przez zestawianie bloków DNF (jak w górnej granicy Marzio) składa się z 13 bramek.

Sprawdziłem, że dla n = 2,3,4,5,6 rozmiary obwodów optymalnych wynoszą 3,5,8,10,12. Wartości te są również rozmiarami obwodów, które dają górną granicę 2,33n. Nadal nie wiem, czy 2,33n jest wielkością obwodu optymalnego dla każdego n. Co więcej, nie znam wielkości obwodu optymalnego dla parzystości 7 zmiennych (są dwie możliwe wartości, 14 i 15).

Ta dolna granica eliminacji bramek nie pasuje do górnej granicy Marzio, ale jest to początek.

$n\ge2$$2n-1$

$3$$n=2$$C$$n>2$

$x_i$$0$

$a$$a=x_1\land x_2\land\cdots$$x_1=0$$a=0$$C'$$x_2$$x_2$$b=\neg x_2\land c_1\land\dots\land c_r$$C'$$c_j$$x_2$$x_3,\dots,x_n$$x_1=0$$c_j$$x_2$$\neg x_2$$C'$$c_j$$1$$b$$\neg x_2$$a$

$2n-1$$\lfloor\frac52n\rfloor-2$

[1] Ingo Wegener, Złożoność funkcji parzystości w nieograniczonych wachlarzach, nieograniczonych obwodach głębokości , Theoretical Computer Science 85 (1991), no. 1, s. 155–170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Rozszerzam swój komentarz:

$k$$k-1$$I_i \geq 2$$g_i$

$3(n-1)$$(x_1,x_2,x_3)$

$5n/2$

Jeśli istnieje literał z 3 rodzicami, możemy wyeliminować wszystkie 3 za pomocą jednej zmiennej.

Jeśli dwa literały występują razem w 2 różnych bramach, razem możemy zastosować główny argument z odpowiedzi Emila, ponownie eliminując 3 bramki za pomocą jednej zmiennej.