Apa kompleksitas Median-SAT?

Misalkan menjadi rumus CNF dengan n variabel dan klausa m . Misalkan t ∈ { 0 , 1 } n mewakili penugasan variabel dan f φ ( t ) ∈ { 0 , ... , m } menghitung jumlah klausa yang dipenuhi oleh penugasan variabel ke φ . Kemudian definisikan Median-SAT sebagai masalah perhitungan nilai median f φ ( t ) di atas semua t ∈ { 0 , $\varphi$$n$$m$$t \in \{ 0,1 \}^n$$f_{\varphi}(t) \in \{ 0, \ldots , m \}$$\varphi$$f_{\varphi}(t)$ . Misalnya, jika φ adalah tautologi maka solusi untuk Median-SAT akan m karena terlepas dari penugasan setiap klausa akan terpenuhi. Namun dalam kasus ¯ S A T solusi untuk Median-SAT bisa di mana saja antara 0 dan m - 1 .$t \in \{ 0,1 \}^n$$\varphi$$m$$\overline{SAT}$$0$$m-1$

Pertanyaan ini muncul ketika saya merenungkan dua ekstensi alami SAT, MAX-SAT dan #SAT, dan apa kesulitan dari masalah yang dihasilkan jika mereka disatukan. Untuk MAX-SAT kita harus menemukan tugas variabel tertentu untuk memaksimalkan jumlah variabel yang dipenuhi oleh . Untuk #SAT kita harus menghitung berapa banyak tugas memenuhi semua m klausul φ . Varian ini berakhir terutama sebagai perpanjangan dari #SAT (dan pada kenyataannya #WSAT ), tetapi mempertahankan beberapa rasa MAX-SAT di mana kita menghitung jumlah klausa yang puas daripada hanya memutuskan apakah mereka semua puas atau tidak.$\varphi$$m$$\varphi$

Masalah ini tampaknya lebih sulit daripada #SAT atau #WSAT. Untuk setiap tugas #SAT variabel memutuskan masalah Boolean apakah yang memenuhi tugas atau tidak sedangkan Median-SAT menentukan "sejauh mana" φ puas dalam hal jumlah klausul bahwa memenuhi tugas.$\varphi$$\varphi$

Saya menyadari bahwa masalah ini agak sewenang-wenang; menghitung rata-rata atau jumlah mode klausa yang dipenuhi oleh setiap penugasan variabel tampaknya menangkap kualitas yang sama. Mungkin banyak masalah lain juga.

Apakah masalah ini telah dipelajari, mungkin dengan kedok yang berbeda? Seberapa sulit dibandingkan dengan #SAT? Tidak jelas bagi saya apriori bahwa Median-SAT bahkan terkandung dalam FPSPACE, meskipun tampaknya terkandung dalam FEXPTIME.

Diberikan instance SAT, integer , dan penugasan variabel, kita dapat memutuskan dalam waktu polinomial apakah tepatnya $k$$k$ klausa terpenuhi, hanya dengan menghitung jumlah klausa yang dipenuhi dan menguji apakah angka itu sama dengan . Oleh karena itu kita dapat menghitung jumlah total variabel assigments yang memenuhi tepat k klausa menggunakan oracle #P .$k$$k$

Jadi seperti Max-SAT, Median-SAT dapat dihitung dalam waktu polinomial menggunakan oracle Ini menunjukkan bahwa masalahnya ada di F P # P ⊆ F P S $\#P$ .$FP^{\#P} \subseteq FPSPACE$

Masalah ini dapat diselesaikan dengan menggunakan doa oracle untuk MAJSAT.$\lceil \lg m+1 \rceil$

Misalkan menunjukkan nilai median yang diinginkan untuk φ . Untuk fixed k , tentukan rumus ψ k sehingga benar untuk penugasan x jika f x memenuhi setidaknya k dari klausa φ . Perhatikan bahwa diberikan φ dalam bentuk CNF dan diberikan k , Anda dapat dengan mudah membuat ψ k dalam bentuk CNF dalam waktu polinomial.$M(\varphi)$$\varphi$$k$$\psi_k$$x$$x$$k$$\varphi$$\varphi$$k$$\psi_k$

Sekarang anggaplah kita memiliki ramalan untuk MAJSAT. Query pada formula akan memberitahu kita apakah mayoritas tugas membuat formula ψ k benar, atau ekuivalen, apakah M ( φ ) ≥ k . Jadi, untuk mempelajari M ( φ ) , terapkan pencarian biner (mulai dengan k = m / 2 , lalu tambah atau kurangi k sesuai dengan hasil dari oracle). Setelah lg m + 1 iterasi, pencarian biner mengungkapkan nilai M ( φ $\psi_k$$\psi_k$$M(\varphi) \ge k$$M(\varphi)$$k=m/2$$k$$\lg m+1$$M(\varphi)$. Setiap iterasi membutuhkan satu permintaan ke oracle kami untuk MAJSAT.