Penyeimbangan rumus Boolean di

10

Saya mencari referensi tentang kompleksitas masalah penyeimbangan rumus Boolean . Khususnya,

  1. Apakah diketahui bahwa rumus Boolean dapat diseimbangkan dalam ?AC0
  2. Apakah ada bukti sederhana keseimbangan Boolean yang menyeimbangkan berada di ?AC0

Maksud "sederhana" yang saya maksud adalah bukti yang lebih sederhana daripada yang saya sebutkan di bawah ini, khususnya saya mencari bukti yang tidak bergantung pada evaluasi rumus Boolean yang ada di .NC1


Latar Belakang

Di sini semua kelas kompleksitas yang disebutkan adalah yang seragam.

BFB (penyeimbangan rumus Boolean):
Diberikan rumus Boolean , Temukan rumus Boolean seimbang yang setara.φ

Saya tertarik dengan kerumitan masalah ini, khususnya bukti sederhana yang menunjukkan masalahnya ada di (atau bahkan atau ). Argumen penyeimbangan umum seperti yang didasarkan pada lemma Spira menerapkan modifikasi struktural berulang pada pohon formula yang tampaknya hanya memberikan . T C 0 N C 1 B F B N C 2AC0TC0NC1BFBNC2

Saya punya bukti untuk , namun buktinya tidak sederhana dan tergantung pada bukti . B F E N C 1BFBAC0BFENC1

BFE (evaluasi rumus Boolean)
Diberikan rumus Boolean dan tugas kebenaran untuk variabel di , Apakah memuaskan ( )?τ φ τ φ τ φφτφ
τφτφ

Diketahui dari hasil terkenal Sam Buss bahwa evaluasi rumus Boolean ( ) dapat dihitung dalam (lihat [Buss87] dan [BCGR92] ).N C 1 = A L o g T i m eBFENC1=ALogTime

Maka (cukup mengejutkan, setidaknya bagi saya) bahwa penyeimbangan formula Boolean ( ) juga dalam :N C 1BFBNC1

Idenya adalah kita dapat melakukan hardcode di gerbang input untuk mendapatkan rumus yang setara dengan dan ini adalah operasi sintaksis yang sepenuhnya dapat dihitung dalam . Karena memiliki rumus seimbang, kami memperoleh rumus seimbang yang setara untuk . Dengan kata lain, algoritma ini adalah:B F E φ A C 0 B F E φφBFEφAC0BFEφ

φλp.Eval(φ,p)

Motivasi

Argumen yang lebih sederhana untuk berada di (atau atau bahkan ) akan memberikan bukti sederhana yang lebih sederhana karena mudah untuk melihat bahwa versi BFE yang seimbang dapat diselesaikan dalam dan kita dapat menyusunnya dengan dan hasilnya akan di .A C 0 T C 0 N C 1 B F E N C 1BFBAC0TC0NC1BFENC1 B F B N C 1NC1BFBNC1


Pertanyaan

  1. Apakah diketahui bahwa rumus Boolean dapat diseimbangkan dalam ( )?AC0BFBAC1
  2. Apakah ada argumen yang lebih sederhana (mis. Tidak mengandalkan ) untuk ?BFENC1BFBAC0
Kaveh
sumber
3
Apa definisi "saldo" yang Anda gunakan?
Dana Moshkovitz
1
@Dana, kita bisa menggunakan sesuatu seperti (yaitu D e p t h = O ( lg S i z e ) dengan konstanta khusus). Lihat juga makalah Bonnet dan Buss " Tradeoff Ukuran-Kedalaman untuk Rumus Boolean ", 2002.Depth<10lgSize+100Depth=O(lgSize)
Kaveh
setuju defn "balancing" harus dibuat jelas. apakah ini mirip dengan konsep keseimbangan dalam pohon biner? mis. "pohon seimbang sendiri"
vzn

Jawaban:

3

Saya tidak yakin apakah ini sangat relevan tetapi dalam Log-Space Algorithms for Paths and Matching in k-Trees (membangun sejarah panjang kerja sebelumnya dan khususnya pada kelas Arithmetizing di sekitar NC1 dan L oleh Limaye-Mahajan-Rao) kami tunjukkan bagaimana menemukan pemisah seimbang rekursif untuk pohon di Logspace. Batas ini mungkin sangat baik untuk jika pohon input langsung diberikan dalam representasi string.NC1

Ide dasarnya adalah untuk mewakili pohon sebagai ekspresi kurung dan menemukan pemisah yang seimbang untuk ini. Perhatikan bahwa kita menemukan pemisah daun yaitu subtree yang seimbang dengan jumlah daun.

SamiD
sumber