Razborov udowodnił, że dopasowanie funkcji monotonicznej nie występuje w MP . Ale czy możemy obliczyć dopasowanie za pomocą obwodu wielkości wielomianowej z kilkoma negacjami? Czy istnieje obwód P / poli z który oblicza dopasowanie? Jaki jest kompromis między liczbą negacji a rozmiarem dopasowania?$O(n^\epsilon)$

Markov udowodnił, że dowolną funkcję danych wejściowych można obliczyć tylko z negacjami ⌈ log ( n + 1 ) ⌉ . Skuteczna wersja konstrukcyjna została opisana przez Fishera. Zobacz także ekspozycję wyniku z bloga GLL .$n$$\lceil \log (n+1)\rceil$

Dokładniej:

Twierdzenie: Załóżmy, że jest obliczany przez obwód C z bramkami g , a następnie jest obliczany przez obwód C ∗ z 2 g + O ( n 2 log 2 n ) bramki i ⌈ log ( n + 1 ) ations negacje.$f : \{0,1\}^n \to \{0,1\}^m$$C$$g$$C^*$$2g + O(n^2 \log^2 n)$$\lceil \log (n+1) \rceil$

Główną ideą jest dodanie dla każdego drutu w C drutu parellelowego w ′ w C ∗, który zawsze przenosi dopełnienie w . Podstawowy przypadek dotyczy przewodów wejściowych: Fisher opisuje, jak zbudować obwód inwersyjny I ( x ) = ¯ x z bramkami O ( n 2 log 2 n ) i tylko negacjami ⌈ log ( n + 1 ) ⌉ . Dla bramek AND obwodu C możemy rozszerzyć $w$$C$$w'$$C^*$$w$$I(x) = \overline x$$O(n^2 \log^2 n)$$\lceil \log (n+1) \rceil$$C$ z a ' = b ' ∨ c " , i podobnie lub bram. NIE bramy w C nic nie kosztują, po prostu zamienić role w i W ' w dół od NOT bramy. W ten sposób cały obwód oprócz obwodu falownika jest monotoniczny.$a = b \land c$$a' = b' \lor c'$$C$$w$$w'$

AA Markov. O złożoności inwersyjnej systemu funkcji. J. ACM , 5 (4): 331–334, 1958.

MJ Fischer. Złożoność sieci o ograniczonej negacji - krótka ankieta. W Automata Theory and Formal Languages , 71–82, 1975

Jak obliczyć inwersję bitów za pomocą n negacji$2^n-1$$n$

Niech bity zostaną posortowane w kolejności malejącej, tj. I < j oznacza x i ≥ x j . Można to osiągnąć dzięki monotonicznej sieci sortującej, takiej jak Ajtai – Komlós – Szemerédi.$x_0, \ldots, x_{2^n-1}$$i<j$$x_i \ge x_j$

Obwód inwersyjny definiujemy dla bitów I n ( → x ) indukcyjnie: W przypadku podstawowym mamy n = 1 i I 1 0 ( → x ) : = ¬ x 0 . Niech m = 2 n - 1 . Zmniejszamy I n (dla 2 m + 1 ) bitów do jednej bramki I n - 1 (dla $2^n-1$$I^n(\vec{x})$$n=1$$I^1_0(\vec{x}) := \lnot x_0$$m=2^{n-1}$$I^n$$2m+1$$I^{n-1}$$m$bitów) i jedna bramka negacji za pomocą bramek i ∨ . Do obliczenia ¬ x m używamy negacji . Dla i < m niech y i : = ( x i ∧ ¬ x m ) ∨ x m + i . Używamy I n - 1 do odwrócenia → y . Teraz możemy zdefiniować I n w następujący sposób:$\land$$\lor$$\lnot x_m$$i<m$$y_i := (x_i \land \lnot x_m) \lor x_{m+i}$$I^{n-1}$$\vec{y}$$I^n$

Łatwo jest zweryfikować to odwrócenie , biorąc pod uwagę możliwe wartości x n i wykorzystując fakt, że → x maleje.$\vec{x}$$x_n$$\vec{x}$

Michael J. Fischer, Złożoność sieci o ograniczonej negacji - krótka ankieta, 1975.