Liczba bramek binarnych potrzebnych do obliczenia AND i OR n bitów wejściowych jednocześnie

Jaka jest minimalna liczba bramek binarnych potrzebnych do jednoczesnego obliczenia AND i OR bitów wejściowych? Trywialna górna granica wynosi . Uważam, że jest to optymalne, ale jak to udowodnić? Nie działa tutaj standardowa technika eliminacji bramki, ponieważ poprzez przypisanie stałej do dowolnej zmiennej wejściowej trywializuje jedno z wyjść. $n$ $2n-2$

Problem podano również jako ćwiczenie 5.12 w książce „Złożoność funkcji boolowskich” autorstwa Ingo Wegenera w nieco innej formie: „Niech . Przez metodą eliminacji można udowodnić tylko dolną granicę wielkości . Spróbuj udowodnić większe dolne granice. ” $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$ $n+\Omega(1)$

cc.complexity-theory lower-bounds circuit-complexity

— Alexander S. Kulikov
źródło

@Ryan: Nie chodzi o I od OR ale o I i OR. Jednak nie znam odpowiedzi na pytanie Sashy.

— Tsuyoshi Ito,

@TsuyoshiIto Dzięki, jakoś udało mi się to parsować niepoprawnie. Jest to zdecydowanie nietrywialny problem - można sobie wyobrazić użycie innego rodzaju bramek, aby uzyskać przewagę nad

2 n - 2

$2n-2$

— Ryan Williams

@Sasha, czy próbowałeś zastosować solwery SAT do małych przykładów (jak

), tak jak w niektórych swoich wcześniejszych artykułach?

n = 4

$n=4$

— Ryan Williams

@ Ryan Tak, jasne. Wiemy, że

. Dotyczy to funkcji z książki (wynosi

iff, wszystkie

bitów wejściowych są równe). Rośnie jak

. A obwód o wielkości

jest łatwy do zbudowania: najpierw obliczyć

dla wszystkich

C_{3} = 3

$C_3=3$

C_{4} = 5

$C_4=5$

C_{5} \leq 7

$C_5 \le 7$

1

$1$

n

$n$

2 n - 3

$2n-3$

2 n - 3

$2n-3$

x_{i} \equiv x_{i + 1}

$x_i \equiv x_{i+1}$

(

bramek), a następnie oblicz ich koniunkcję (

bramek).

i = 1, \dots, n - 1

$i=1,\dots,n-1$

(n - 1)

$(n-1)$

(n - 2)

$(n-2)$

— Alexander S. Kulikov,

@Tsuyoshi: Myślę, że funkcja bramek

Sashy jest drugą funkcją pytania (

), którą można zbudować za pomocą

bramki XNOR (zastosowane do

) oraz

ORAZ bramki zastosowane do XNOR.

2 n - 3

$2n-3$

f_{n} (x) = x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$

n - 1

$n-1$

x_{i}, x_{i + 1}

$x_i,x_{i+1}$

n - 2

$n-2$

— Marzio De Biasi,

Odpowiedzi:

Ten artykuł Blum & Seysen może być przydatny:

N.Blum, M. Seysen. Charakterystyka wszystkich sieci optymalnych do jednoczesnego obliczania AND i NOR . Acta Inf. 21: 171–181 (1984)

Myślałem, że dla dolną granicę można uzyskać metodami Bluma i Seysena, ale wydaje się, że tak nie jest. $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$

— Vladimir Lysikov
źródło

Czy jest dostępna publiczna wersja pdf artykułu Blum i Seysen?

— Marzio De Biasi,

@Vladimir, dziękuję za odniesienie! Postaram się sprawdzić, czy ich metody mają zastosowanie w tym przypadku, gdy znajdę artykuł.

— Alexander S. Kulikov,

@Vladimir, dzięki jeszcze raz! W rzeczywistości ten artykuł zawiera dokładnie odpowiedź na moje pytanie i jeszcze bardziej: mówi, że do obliczenia AND i OR jednocześnie potrzebne są

i każdy obwód tego rozmiaru oblicza AND i OR niezależnie (to ciekawe!). Nie jest również trudne do wykazania, że

2 n - 2

$2n-2$

C (f_{n}) \geq C (A N D, O R) - c \geq 2 n - c^{'}

$C(f_n) \ge C(AND,OR)-c \ge 2n-c'$

— Alexander S. Kulikov,

@Sasha, tak, brakowało mi tej prostej konstrukcji. Aby to wyjaśnić, w artykule rozważono funkcje AND i NOR, więc dla AND i OR otrzymujemy

dolną granicę poprzez zmianę jednej bramki i dla

---

2 n - 2

$2n-2$

x_{1} \dots x_{n} \lor {\bar{x}}_{1} \dots {\bar{x}}_{n}

$x_1\dots x_n\vee \bar{x}_1\dots \bar{x}_n$

2 n - 5

$2n-5$

— Vladimir Lysikov,

Przypomnienie @SashaK. jeśli podoba Ci się odpowiedź, „zaakceptuj” ją, klikając znacznik pod liczbą głosów.

— Suresh Venkat,

Twoje pytanie wiąże się ze znanym pytaniem dotyczącym obliczania minimalnej i maksymalnej liczby list jednocześnie przy użyciu minimalnej liczby porównań. W takim przypadku odpowiedź wynosi . $3\lfloor n/2 \rfloor$

Sprytny algorytm potwierdzający górną granicę przekłada się na obwód AND / OR z tą samą granicą, którą otrzymujesz, ponieważ jedno z porównań oblicza zarówno minimum, jak i maksimum.

Jednak dolna granica (podana przez argument przeciwnika) wydaje się tłumaczyć, przynajmniej w przypadku obwodów monotonicznych (ponieważ obwód AND / OR przekłada się na algorytm max / min). Oznaczałoby to dolną granicę . Być może można uzyskać ścisłą dolną granicę, analizując argument przeciwnika. $3\lfloor n/2 \rfloor$

Górna granica pojawia się w „Wprowadzenie do algorytmów”, gdzie można również znaleźć prosty argument pokazujący, że obwody komparatora maks./min są prawidłowe, jeśli działają dla wejść logicznych (należy zastosować odpowiedni próg). Dolną granicę można znaleźć np . Tutaj .

— Yuval Filmus
źródło

Zauważ, że w pytaniu Sashy wszystkie 2-bitowe funkcje boolowskie mogą być użyte do budowy obwodu.

— Ryan Williams,

Tak, nie jest jasne, w jaki sposób dolną granicę można przełożyć na przypadek wszystkich funkcji binarnych.

— Alexander S. Kulikov,