Jumlah gerbang biner yang diperlukan untuk menghitung AND dan OR dari n bit input secara bersamaan

Berapa jumlah minimal gerbang biner yang diperlukan untuk menghitung AND dan OR dari bit input secara bersamaan? Batas atas sepele adalah . Saya percaya ini optimal, tetapi bagaimana cara membuktikannya? Teknik eliminasi gerbang standar tidak berfungsi di sini karena dengan menetapkan konstanta pada salah satu variabel input yang diremehkan salah satu output. $n$ $2n-2$

Masalahnya juga diberikan sebagai latihan 5.12 dalam buku "Complexity of Boolean Functions" oleh Ingo Wegener dalam bentuk yang sedikit berbeda: "Biarkan . Oleh metode eliminasi yang dapat dibuktikan hanya dengan batas bawah ukuran . Cobalah untuk membuktikan batas bawah yang lebih besar. " $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
sumber

@Ryan: Pertanyaannya bukan tentang DAN dari OR tetapi tentang DAN dan ATAU. Saya tidak tahu jawaban untuk pertanyaan Sasha.

Tsuyoshi Ito

@TsuyoshiIto Terima kasih, entah bagaimana saya berhasil menguraikannya dengan tidak benar. Ini jelas merupakan masalah nontrivial - orang bisa membayangkan menggunakan jenis gerbang lain untuk mendapatkan keuntungan lebih dari

2 n - 2

$2n-2$

Ryan Williams

@ Sasha, sudahkah Anda mencoba menerapkan solver SAT ke contoh kecil (seperti

), seperti pada beberapa makalah Anda sebelumnya?

n = 4

$n=4$

Ryan Williams

@Ryan Ya, tentu. Yang kita tahu adalah bahwa

. Ini untuk fungsi dari buku (ini adalah

iff semua

input bits sama). Ini tumbuh seperti

. Dan sirkuit dari ukuran

mudah untuk membangun: pertama menghitung

untuk semua

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}$

(

gerbang), dan kemudian menghitung hubungannya dengan mereka (

gerbang).

i = 1, \dots, n - 1

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

(n - 1)

$(n-1)$

(n - 2)

$(n-2)$

Alexander S. Kulikov

@Tsuyoshi: Saya berpikir bahwa

gerbang berfungsi dari Sasha adalah fungsi kedua pertanyaan (

) yang dapat dibangun dengan

gerbang XNOR (diterapkan pada

) dan gerbang

AND yang diterapkan pada 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

Jawaban:

Makalah Blum & Seysen ini mungkin berguna:

N.Blum, M. Seysen. Karakterisasi semua Jaringan Optimal untuk Perhitungan Simultan AND dan NOR . Acta Inf. 21: 171-181 (1984)

Saya telah berpikir bahwa untuk batas bawah dapat diperoleh dengan menggunakan metode Blum & Seysen, tetapi tampaknya ini tidak terjadi. $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$

Vladimir Lysikov
sumber

Apakah ada versi pdf publik dari kertas Blum dan Seysen yang tersedia?

Marzio De Biasi

@Vladimir, terima kasih untuk referensi! Saya akan mencoba memeriksa apakah metode mereka berlaku dalam hal ini ketika menemukan artikel.

Alexander S. Kulikov

@Vladimir, terima kasih lagi! Sebenarnya, makalah ini mengandung jawaban yang tepat untuk pertanyaan saya bahkan lebih lagi: ia mengatakan bahwa untuk menghitung AND dan OR secara bersamaan seseorang membutuhkan

dan setiap sirkuit dengan ukuran ini menghitung AND dan OR secara mandiri (ini menarik!). Juga tidak sulit untuk menunjukkan bahwa

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, ya, saya melewatkan konstruksi sederhana ini. Untuk mengklarifikasi hal-hal, di koran fungsi AND dan NOR dipertimbangkan, jadi untuk AND dan OR kita mendapatkan

batas bawah dengan mengubah satu gerbang dan untuk

---

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

Hanya pengingat @SashaK. jika Anda menyukai jawabannya, silakan "menerimanya" dengan mengklik tanda centang di bawah penghitungan suara.

Suresh Venkat

Pertanyaan Anda terkait dengan pertanyaan terkenal tentang menghitung minimum dan maksimum daftar secara bersamaan menggunakan jumlah perbandingan minimum. Dalam hal ini jawabannya adalah . $3\lfloor n/2 \rfloor$

Algoritme pintar yang membuktikan batas atas diterjemahkan menjadi sirkuit AND / OR dengan batas yang sama yang Anda dapatkan, karena salah satu perbandingan menghitung minimum dan maksimum.

Namun, batas bawah (diberikan oleh argumen musuh) tampaknya menerjemahkan, setidaknya dalam kasus sirkuit monoton (karena sirkuit AND / OR diterjemahkan menjadi algoritma max / min). Ini akan menyiratkan batas bawah . Mungkin batas bawah yang ketat dapat diperoleh dengan menganalisis argumen musuh. $3\lfloor n/2 \rfloor$

Batas atas muncul di "Pengantar Algoritma", di mana Anda juga dapat menemukan argumen mudah yang menunjukkan bahwa sirkuit komparator maks / mnt valid jika mereka bekerja untuk input boolean (gunakan ambang batas yang sesuai). Batas bawah dapat ditemukan misalnya di sini .

Yuval Filmus
sumber

Catatan dalam pertanyaan Sasha, semua fungsi Boolean 2-bit dapat digunakan untuk membangun sirkuit.

Ryan Williams

Ya, tidak jelas bagaimana batas bawah dapat diterjemahkan ke kasus semua fungsi biner.

Alexander S. Kulikov