Kompleksitas meminimalkan ukuran formula polinom

28

Misalkan menjadi derajat polinomial dalam variabel lebih dari , di mana adalah konstan (katakanlah 2 atau 3). Saya ingin mencari rumus terkecil untuk , di mana "rumus" dan "ukuran rumus" didefinisikan dengan cara yang jelas (mis. Rumus terkecil untuk polinomial adalah ). $f(x_1,\dots,x_n)$ $d$ $n$ $\mathbb{F}_2$ $d$ $f$ $x_1 x_2 + x_1 x_3$ $x_1(x_2+x_3)$

Apa kompleksitas masalah ini - apakah ini NP-hard? Apakah kompleksitasnya bergantung pada ? $d$

[Lebih formal, rumus (alias "rumus aritmatika") adalah pohon biner yang di-root, masing-masing yang daunnya dilabeli dengan variabel input atau konstanta 1. Semua simpul lain dari pohon tersebut diberi label dengan atau . Ukuran formula adalah jumlah daun yang digunakan. Rumus menghitung polinomial secara rekursif: simpul menghitung jumlah anak-anak mereka lebih dari , simpul menghitung produk. ] $+$ $\times$ $+$ $\mathbb{F}_2$ $\times$

cc.complexity-theory formulas Ashley Montanaro
sumber

1

tidak bisakah kita mengurangi pengujian identitas polinomial untuk masalah ini?

Kaveh

4

Saya kira mungkin ada koneksi, tetapi saya tidak segera melihatnya - khususnya karena kendala pada derajat. Selain itu, jika masalahnya lebih sulit daripada pengujian identitas polinomial, akan menarik untuk mengetahui seberapa jauh lebih sulit.

Ashley Montanaro

Dalam kasus Anda, bagaimana jumlah gerbang (

s, dan

s) dalam rumus terkait dengan ukuran rumus aktual? Untuk

, konstruksi dalam Ehrenfeucht dan Karpinski 90 tampaknya relevan (lihat paragraf 2XOR) untuk ukuran formulasi "gate", tetapi saya harus memikirkannya lebih lama.

+

$+$

\times

$\times$

d = 2

$d=2$

Alessandro Cosentino

Karena rumusnya adalah pohon biner, definisi ukuran formula yang saya gunakan di sini (jumlah daun) sama dengan jumlah gerbang (simpul internal) ditambah satu. Tetapi saya akan tertarik pada hasil apa pun untuk definisi ukuran formula yang masuk akal lainnya juga. Saya tidak yakin saya melihat koneksi ke hasil Ehrenfeucht dan Karpinski, karena ini adalah tentang kompleksitas penghitungan solusi, daripada meminimalkan ukuran formula ...

Ashley Montanaro

Untuk menghitung jumlah nol, mereka pertama-tama mengubah rumus menjadi setara, yang saya ingat minimum dalam hal perkalian dan penambahan. Saya tidak punya bukti minimalitas ini. Sekali lagi, ini hanya akan menjawab kasus

.

d = 2

$d=2$

Alessandro Cosentino

7

Anda dapat mengurangi masalah TAUTOLOGI Ko-NP-Lengkap (diberikan rumus Boolean, apakah ini tautologi?) Menjadi masalah meminimalkan ukuran rumus (karena rumus adalah tautologi jika setara dengan BENAR). Selain itu, TAUTOLOGI untuk 3DNF (analog dengan SAT untuk 3CNF) adalah co-NP-Complete.

Dana Moshkovitz
sumber

1

Seperti yang saya pahami pertanyaannya,

harus dihitung sebagai polinomial bukan sebagai fungsi. Mungkin diperlukan klarifikasi.

f

$f$

Markus Bläser

3

Ada pengurangan probabilistik dari 3SAT ke pengecekan, diberi polinomial deg-3 di atas GF (2), apakah ia memiliki nol [dengan melihat kombinasi linear acak dari klausa], dan kemudian dari ini ke pengecekan, diberi deg- 3 poli di atas GF (2), apakah semuanya nol [dengan mengurangi poli dari 1].

Dana Moshkovitz

1

Terima kasih! Apakah Anda tahu apa situasinya untuk polinomial tingkat 2? Juga (meskipun ini mungkin sangat padat) Saya berjuang untuk melihat bagaimana gelar 3 jumlahnya banyak daripada GF (2), yang ditulis dalam bentuk standar, dapat semuanya nol tanpa menjadi nol jumlahnya banyak. Agar lebih jelas, saya membayangkan bahwa input untuk masalah saya adalah deskripsi polinomial itu sendiri, bukan deskripsi sirkuit yang menghitung polinomial.

Ashley Montanaro

2

Sekali lagi terima kasih atas balasan Anda. Saya masih tidak yakin tentang hal yang sepenuhnya nol; menurut saya bahwa setiap polinomial n-variate lebih dari GF (2) dengan poli (n) dapat dengan mudah diubah menjadi bentuk standar di mana jelas apakah polinomialnya nol atau tidak, hanya dengan membuat substitusi

dan mengumpulkan istilah.

x^{k} \to x

$x^k \rightarrow x$

Ashley Montanaro

4

Memang jika Anda membuatnya multilinear seperti yang Anda jelaskan, polinomial bernilai nol pada setiap input jika itu adalah polinomial nol. Satu bukti: Pilih monomial non-nol derajat minimal. Setel ke nol semua variabel lainnya. Satu-satunya monomial yang masih hidup adalah M. Dengan mengatur vars di M ke 1 Anda mendapatkan output yang tidak nol.

Manu

4

Tidak persis jawabannya tetapi mudah-mudahan membantu:

Pertanyaan ini harus NP sulit untuk d = 2 jika Anda ingin tahu rumus minimal untuk polinomial dan bukan hanya untuk satu. Buktinya adalah sebagai berikut: Ada korespondensi satu ke satu antara n bi-linear formula (rumus jenis ) dan tensor 3 matriks yaitu elemen dalam . Sedemikian rupa sehingga tensor rank dari matriks adalah kompleksitas multiplikasi dari rumus n-linear. $n$ $\sum a_{ij}x_iy_j$ $F_2^n\otimes F_2^n\otimes F_2^n$

Diketahui bahwa tensor rank adalah masalah NP-hard (mungkin kira-kira rank tensor juga NP-hard). Jadi kompleksitas multiplikasi formula -linear adalah masalah NP-hard $3$ $n$

Klim
sumber

2

Terima kasih! Ini adalah perspektif yang menarik tentang masalahnya.

Ashley Montanaro

Teorema berikut membantu untuk beralih dari banyak polinomial ke satu polinomial: LEt S (f) kompleksitas satu polinomial kemudian kompleksitas penghitungan semua turunannya paling banyak adalah 5S (f). Jadi polinomial kompleksitas

hampir sama dengan kompleksitas

f_{1}, f_{2}, \dots, f_{n}

$f_1, f_2,\ldots,f_n$

z_{1} f_{1} + z_{2} f_{2} \dots z_{n} f_{n}

$z_1f_1+z_2f_2\ldots z_n f_n$

Klim

Jika Anda berbicara tentang peringkat tensor, maka Anda hanya menghitung perkalian tetapi bukan penambahan. Kasus

dan hanya satu bentuk bilinear mudah maka, karena seseorang dapat menghitung peringkat satu bentuk bilinear, dengan menggunakan teorema struktur yang disebutkan dalam jawaban Ramprasad. (Bukti-bukti dari teorema ini bersifat algoritmik, lihat buku oleh Lidl & Niederreiter.)

d = 2

$d = 2$

Markus Bläser

2

Setiap jawaban untuk ini sangat tergantung pada kosakata yang Anda izinkan dalam jawabannya. Jika Anda ingin jawaban Anda dalam bahasa yang sama dengan input (yaitu sebagai polinomial), itu mengarah ke satu set jawaban, yang merupakan jawaban dari poster lain.

Tetapi jika Anda membiarkan perbendaharaan jawaban Anda diperbesar, hal-hal indah dapat terjadi. Anda dapat melihat contoh dalam diferensiasi simbolis vs otomatis: dalam diferensiasi simbolis satu hanya memungkinkan 'ekspresi', yang cenderung meledak sangat buruk; dalam diferensiasi otomatis, seseorang memungkinkan program garis lurus dalam jawabannya (bahkan jika inputnya adalah ekspresi), yang sangat membantu untuk mengendalikan pembengkakan ekspresi. Untuk polinomial univariat, James Davenport dan saya telah merenung bahwa Anda perlu memasukkan polinomial siklotomik sebagai bagian dari kosakata dasar Anda juga (lihat referensi mengapa polinomial ini tampaknya menjadi satu-satunya sumber blow-up yang nyata, serta makalah yang menunjukkan berbagai hasil reducibilitas antara masalah polinomial dan 3SAT).

Dengan kata lain, jika Anda membiarkan diri Anda sedikit mengubah apa yang Anda anggap sebagai jawaban sedikit dari yang klasik, Anda mungkin hanya bisa mendapatkan jawaban yang agak berbeda, yaitu yang dengan kompleksitas yang jauh lebih baik. Tergantung pada motivasi awal Anda untuk mengajukan pertanyaan, apakah murni teoretis atau dengan aplikasi dalam pikiran, untuk memutuskan apakah variasi dalam kosa kata ini dapat Anda terima. Dalam pengaturan di mana James dan saya telah memikirkan hal ini (perhitungan simbolik), menyesuaikan kosakata untuk membuat penurunan kompleksitas sangat dapat diterima (meskipun jarang dilakukan).

Jacques Carette
sumber

Pertanyaannya menanyakan rumus aritmatika terkecil, yang kemudian didefinisikan dengan jelas. Karena itu saya tidak yakin balasan ini relevan secara langsung. Juga, jawaban di atas oleh Dana Moshkovitz dan komentar terkait tidak dengan benar menjawab pertanyaan sebagaimana telah diakui dalam komentar.

Raphael

Inti dari jawaban saya adalah bahwa OP mungkin tidak menyadari bahwa mereka tidak perlu menanyakan pertanyaan terbaik. Pertanyaan OP ditanyakan dalam istilah yang sangat klasik, tetapi jika Anda membiarkan sedikit penyimpangan dari itu, Anda mendapatkan jawaban yang sangat berbeda, yang mungkin sangat tidak terduga. Saya mengerti komentar Anda, tetapi merasa downvote agak keras.

Jacques Carette

Bisakah Anda memperbaiki paragraf pertama dari jawaban Anda untuk memperjelas pertanyaan yang belum dijawab dengan benar? Saya khawatir orang akan menyesatkan.

Raphael

1

@ Raphael: selesai. Dan mengklarifikasi lebih jauh juga.

Jacques Carette

0

Minimalisasi sirkuit / formula umum tentu saja lebih sulit daripada pengujian identitas, karena ukuran formula minimum identitas apa pun hanyalah nol. Adapun seberapa sulit, saya tidak memiliki jawaban yang pasti, tetapi mungkin "algoritma rekonstruksi" yang dipelajari di sirkuit / rumus aritmatika mungkin menjadi sesuatu di sepanjang baris ini.

$\mathcal{C}$ $3$ $\mathcal{C}$

$d$

$d=2$ $x_1x_2 + x_3x_4 + .. + x_{2k-1}x_{2k} + \ell$

Ramprasad
sumber

Terima kasih atas komentar anda Sayangnya, saya tidak melihat bagaimana menggunakan ide-ide ini untuk menyelesaikan masalah aslinya.

Ashley Montanaro

Kompleksitas meminimalkan ukuran formula polinom

Jawaban: