Sirkuit aritmatika dengan

Pertimbangkan rangkaian yang mengambil sebagai input angka dalam $[0,1]$ , dan memiliki gerbang yang terdiri dari fungsi $\max(x, y)$ , $\min(x, y)$ , $1 - x$ , dan $\frac{x+y}{2}$ . Output dari rangkaian kemudian juga angka dalam $[0,1]$ .

Adakah yang tahu kalau model ini, atau model yang berkaitan erat, telah dipelajari?

Secara khusus, saya mencoba untuk memecahkan masalah kepuasan untuk sirkuit ini, yaitu menghitung nilai maksimum yang dapat dicapai oleh sirkuit ini (itu memang mencapai maksimum, karena itu merupakan fungsi kontinu dalam domain kompak).

Catatan: studi saya tentang model ini adalah melalui logika temporal tertimbang, sehingga setiap model yang berhubungan dengan yang terakhir mungkin juga berguna.

arithmetic-circuits Shaull
sumber

Tentunya masalah ini NP-hard. (Melalui kepuasan: Anda memiliki

x \lor y \equiv max {x, y}

$x\vee y \equiv \max\{x,y\}$ dan

\neg x \equiv 1 - x

$\neg x \equiv 1 - x$ , yang dengannya Anda dapat melakukan AND, ATAU, dan TIDAK.) Jadi, pertanyaan Anda adalah apakah atau tidak masalah ini di NP? Pertanyaan keputusan apakah rangkaian seperti itu memiliki input yang menghasilkan nilai 1 tampaknya berada di NP, karena, jika ada input seperti itu, ada satu yang 0/1.

Neal Young

Jika kita tidak menentukan secara pasti salah satu dari kemungkinan nilai kebenaran untuk , di mana adalah semua pasangan node sedemikian sehingga simpul atau muncul di sirkuit, ini berubah menjadi masalah pemrograman linier, yang dipecahkan dalam P. Dengan demikian, versi keputusan masalah maksimisasi asli adalah dalam NP. (Ini adalah varian dari masalah kepuasan dalam logika Łukasiewicz, jadi Anda mungkin ingin melihat bab Haniková dalam Buku Pegangan Logika Fuzzy Matematika untuk informasi terkait.)

\leq 2^{n}

$\le2^n$

x \leq y

$x\le y$

x, y

$x,y$

min (x, y)

$\min(x,y)$

max (x, y)

$\max(x,y)$

Emil Jeřábek

@ Samull: Izinkan saya menggambarkannya dengan lebih rinci. Misalkan menjadi simpul dari rangkaian yang merupakan gerbang min atau maks (di sini dibatasi oleh ukuran rangkaian), dan biarkan dan menjadi simpul input gerbang . Untuk setiap , pilih kendala tambahan atau . Ada pilihan seperti itu. Ketika pilihan seperti itu diperbaiki, Anda dapat menyederhanakan sirkuit dengan mengganti dengan atau

{a_{i} : i < m}

$\{a_i:i<m\}$

m

$m$

b_{i}

$b_i$

c_{i}

$c_i$

a_{i}

$a_i$

i < m

$i<m$

b_{i} \leq c_{i}

$b_i\le c_i$

c_{i} \leq b_{i}

$c_i\le b_i$

2^{m}

$2^m$

a_{i}

$a_i$

b_{i}

$b_i$

c_{i}

$c_i$ jika sesuai, maka itu berubah menjadi sistem persamaan linear yang variabelnya adalah variabel asli dari masalah, dan variabel tambahan yang sesuai dengan ...

Emil Jeřábek

... node dalam rangkaian. Sertakan ketidaksetaraan yang menyatakan bahwa kendala tambahan dipenuhi, ketidaksetaraan mengikat variabel asli ke , dan ketidaksetaraan yang menyatakan bahwa simpul keluaran memiliki nilai . Maka ini adalah program linier tergantung pada pilihan kendala tambahan, dan sirkuit mendapatkan nilai iff ada pilihan kendala sehingga program linier terkait memiliki solusi.

m

$m$

[0, 1]

$[0,1]$

\geq u

$\ge u$

\geq u

$\ge u$

Emil Jeřábek

Perhatikan juga bahwa nilai optimal dari program linier diperoleh pada titik puncak polytope. Ini berarti bahwa penyebut dari solusi optimal dapat dinyatakan sebagai penentu matriks dimensi yang entri adalah bilangan bulat ukuran konstan, dan hanya ada entri bukan nol di setiap baris, dan dengan demikian dibatasi oleh .

O (n)

$O(n)$

O (1)

$O(1)$

2^{O (n)}

$2^{O(n)}$

Emil Jeřábek

Jawaban:

Masalah kepuasan untuk sirkuit ini (yaitu, diberi sirkuit dan , memutuskan apakah ada input sehingga ) berada di NP, dan karenanya NP-diisi oleh Komentar Neal Young dan jawaban Peter Shor. $C$ $u\in[0,1]$ $x$ $C(x)\ge u$

Kita dapat membangun pengurangan masalah yang tidak ditentukan untuk pemrograman linear dengan cara berikut. Biarkan menjadi semua simpul yang merupakan gerbang min atau maks (di sini , di mana adalah ukuran sirkuit), dan biarkan dan menjadi simpul input gerbang . Untuk setiap , pilih salah satu dari dua batasan tambahan atau (ada kemungkinan pilihan secara total). Ketika pilihan seperti itu diperbaiki, kita dapat menyederhanakan sirkuit dengan mengganti setiap dengan atau $\{a_i:i<m\}$ $C$ $m\le n$ $n$ $b_i$ $c_i$ $a_i$ $i<m$ $b_i\le c_i$ $c_i\le b_i$ $2^m$ $a_i$ $b_i$ $c_i$ sebagaimana layaknya, dan sirkuit yang dihasilkan dapat dijelaskan oleh sistem persamaan linear yang variabel-variabelnya adalah variabel input asli dari sirkuit, dan variabel tambahan yang sesuai dengan simpul-simpul sirkuit. $n$

Kami juga menyertakan ketidaksetaraan yang menyatakan bahwa kendala ekstra puas, ketidaksetaraan berlari variabel input asli untuk , dan ketimpangan yang menyatakan bahwa output node memiliki nilai . Maka ini adalah program linier ukuran tergantung pada pilihan kendala tambahan, dan sirkuit mencapai nilai iff jika ada pilihan kendala sehingga program linier terkait memiliki solusi. Karena pemrograman linear dalam P, ini menunjukkan bahwa masalahnya ada di NP. $m$ $[0,1]$ $\ge u$ $O(n)$ $\ge u$

Perhatikan juga bahwa nilai optimal dari program linier diperoleh pada titik puncak polytope. Ini berarti bahwa penyebut dari solusi optimal dapat dinyatakan sebagai penentu matriks kuadrat dimensi yang entri-entrinya adalah bilangan bulat ukuran konstan, dan hanya ada entri bukan nol di setiap baris, dan dengan demikian itu dibatasi oleh . $O(n)$ $O(1)$ $2^{O(n)}$

Pengurangan semacam ini sering berguna untuk memberikan batas atas pada kompleksitas kepuasan dalam logika fuzzy proposisional (seperti logika Łukasiewicz) dan sistem terkait. (Faktanya, masalah awal adalah varian minor dari kepuasan dalam Łukasiewicz, yang akan sesuai dengan sirkuit dengan alih-alih ) Tinjauan umum hasil terkait dapat ditemukan dalam Bab X dari Buku Pegangan Matematika Fuzzy Logic, Vol. II $\min(1,x+y)$ $(x+y)/2$

Emil Jeřábek
sumber

Masalah ini NP-hard.

Anda bisa mendapatkan 3-SAT dengan gerbang min ( x , y ), maks ( x, y ) dan 1− x .

Yang kami inginkan adalah mengurangi masalah 3-SAT ke sirkuit yang Anda bisa dapatkan 1 jika semua variabel memuaskan, dan Anda hanya bisa mencapai sesuatu yang benar-benar kurang dari 1 jika tidak.

Kami dapat memaksa semua variabel menjadi 0 atau 1 dengan mengambil minimum banyak ekspresi, dan membuat ekspresi ini termasuk maks ( x , 1− x ).

Sekarang untuk setiap klausa dalam masalah 3-SAT x ∨ y ∨ z , kami menempatkan ekspresi max ( x , y , z ) dalam minimum.

Saya tidak tahu apa nilai optimal untuk masalah 3-SAT yang tidak memuaskan, tetapi akan benar-benar kurang dari 1.

Peter Shor
sumber

Ya, NP-hardness adalah "arah yang mudah", seperti yang ditunjukkan dalam komentar di atas. Bahkan, jika Anda tidak menggunakan gerbang rata-rata, tetapi hanya min dan maks, mudah untuk menunjukkan bahwa nilai maksimal adalah 1 jika rangkaian Boolean yang sesuai memuaskan, dan 1/2 jika tidak (hanya dengan menghubungkan 1/2 ke semua variabelnya). Lagi pula, masalah itu diselesaikan dalam komentar di atas.

Shaull

Tidak persis apa yang Anda minta, tetapi konteks di mana sirkuit serupa muncul.

Jika Anda menghapus gerbang (yang bahkan tidak disebutkan dalam judul!) Maka apa yang Anda dapatkan adalah rangkaian aritmatika monoton. Sirkuit monoton klasik batas bawah Razborov telah diperluas ke sirkuit aritmatika monoton (dengan hasil yang sama) oleh Pavel Pudlák, Batas bawah untuk resolusi dan memotong bukti pesawat . $1-x$

Yuval Filmus
sumber

Terima kasih. Namun dalam kasus ini, jika Anda menghapus gerbang , maka masalahnya adalah sepele - nilai maksimalnya adalah 1 dan tercapai ketika semua variabel mendapatkan nilai 1.

1 - x

$1-x$

Shaull