Karakterisasi formula baca-sekali atas basis biner penuh

15

Latar Belakang

Rumus baca-sekali atas satu set gerbang (juga disebut basis) adalah rumus di mana setiap variabel input muncul satu kali. Rumus baca-sekali biasanya dipelajari atas dasar De Morgan (yang memiliki gerbang 2-bit AND dan OR, dan gerbang 1-bit TIDAK) dan basis biner penuh (yang memiliki semua gerbang 2-bit).

Jadi misalnya, AND dari 2 bit dapat ditulis sebagai rumus baca-sekali atas kedua basis, tetapi paritas 2 bit tidak dapat ditulis sebagai rumus baca-sekali atas dasar De Morgan.

Himpunan semua fungsi yang dapat ditulis sebagai rumus baca-sekali atas dasar De Morgan memiliki karakterisasi kombinatorial. Lihat, misalnya, karakterisasi kombinatorial rumus baca-sekali oleh M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.

Pertanyaan

Apakah ada karakterisasi alternatif dari himpunan fungsi yang dapat dihitung dengan rumus baca-sekali atas basis biner penuh?

Pertanyaan Lebih Mudah (ditambahkan dalam v2)

Sementara saya masih tertarik pada jawaban untuk pertanyaan asli, karena saya belum menerima jawaban, saya pikir saya akan mengajukan pertanyaan yang lebih mudah: Apa sajakah teknik batas bawah yang bekerja untuk rumus di atas basis biner penuh? (Selain yang saya sebutkan di bawah ini.)

Perhatikan bahwa sekarang saya mencoba untuk membatasi ukuran formula (= jumlah daun) lebih rendah. Untuk rumus baca-sekali, kami memiliki ukuran rumus = jumlah input. Jadi jika Anda dapat membuktikan bahwa suatu fungsi membutuhkan rumus ukuran yang lebih besar dari n, maka itu juga berarti tidak dapat direpresentasikan sebagai rumus baca-sekali.

Saya mengetahui teknik-teknik berikut (bersama dengan referensi untuk setiap teknik dari Kompleksitas Fungsi Boolean: Kemajuan dan Batas oleh Stasys Jukna ):

  • Metode Nechiporuk untuk fungsi universal (Bagian 6.2): ​​Memperlihatkan batas bawah ukuran untuk fungsi tertentu. Ini tidak membantu Anda menemukan batas bawah untuk fungsi tertentu yang mungkin Anda minati.n2−o(1)
  • Ω(n2/log⁡n)
cc.complexity-theory circuit-complexity lower-bounds formulas Robin Kothari
sumber
Sudahkah Anda melihat BDD, diagram keputusan biner ? bukankah mereka cukup dekat dalam kompleksitas? tapi, belum melihat spec ref pada subj.
vzn

Jawaban:

-2

ada juga metode yang disebut Krapchenko batas bawah "yang bisa sedikit lebih besar dari metode Nechiporuks". lihat John E Savage, Model Komputasi, bagian 9.4.2. (yang tercakup tepat setelah metode Nechiporuk di bagian 9.4.1)

vzn
sumber
2
Terima kasih untuk referensi, tetapi metode Krapchenko hanya bekerja di atas dasar De Morgan (disebut "basis standar" dalam buku Savage). Pertanyaan saya adalah tentang basis biner penuh.
Robin Kothari
jika metode Nechiporuks bekerja dengan basis biner penuh & metode ini terbukti bekerja dengan basis De Morgan / standar dalam buku Savages, mengapa Krapchenkos tidak bekerja pada keduanya juga? tetapi Savage setuju tidak memiliki contoh basis Krapchenko / biner penuh.
vzn
1
Basis biner penuh adalah superset dari basis De Morgan. Setiap batas bawah yang bekerja melawan basis biner penuh juga bekerja melawan basis De Morgan.
Robin Kothari
ok, baik, apa yang mengesampingkan metode Krapchenko yang bekerja secara biner penuh? Saya curiga metode Nechiporuk mungkin pertama diterapkan pada basis de Morgan & kemudian diperluas ke basis penuh, benar? apa yang mengesampingkan metode Krapchenko?
vzn