Apakah ada algoritma yang efisien untuk ekuivalensi ekspresi?

14

misal ?xy+x+y=x+y(x+1)

Ekspresi berasal dari aljabar sekolah menengah biasa, tetapi terbatas pada penambahan dan perkalian aritmatika (misalnya ), tanpa inversi, pengurangan atau pembagian. Surat adalah variabel.2+2=4;2.3=6

Jika ini membantu, kami dapat melarang ekspresi apa pun yang dapat diwakili dengan nilai numerik selain ; yaitu bukan atau atau :x 2 3 x 41x23x4

  • multilinear , tidak ada kekuatan selain : tidak apa-apa, tetapi tidak , dan bukan apa pun yang dapat direpresentasikan seperti itu, seperti dalam ekspansi penuh ke jumlah produk misalnya bukan ; x + x y x 1 + x 1 y 1 x 2 + x 3 y 4 x ( x + y ) x 2 + y1x+xyx1+x1y1x2+x3y4x(x+y)x2+y
  • semua satu , tidak ada koefisien selain : OK, tetapi tidak , dan bukan apa pun yang dapat direpresentasikan seperti itu, seperti dalam ekspansi penuh ke jumlah produk misalnya bukan ; dan 1x+xy1.x+1.xy2x+3xya(x+y)+x(a+b)2ax+ay+bx
  • tidak ada konstanta selain : lagi, dalam penjumlahan produk yang diperluas sepenuhnya mis. tidak1(a+1)+(b+1)a+b+2

Q. Apakah ada algoritma yang efisien untuk menentukan apakah dua ekspresi setara?


Sebagai ilustrasi, berikut ini adalah algoritma brute-force yang tidak efisien dengan waktu eksponensial:

perluas kedua ekspresi sepenuhnya menjadi jumlah produk , yang dapat dengan mudah diperiksa kesetaraannya (abaikan saja pesanan, karena perjalanan / rekan dapat memesan ulang).

mis.
(a+b)(x+y)ax+ay+bx+by
a(x+y)+b(x+y)ax+ay+bx+by


Ini tampaknya masalah yang terkenal - bahkan siswa sekolah menengah diajarkan cara manual untuk menyelesaikannya. Ini juga diselesaikan oleh pembalik / pemeriksa teorema otomatis, tetapi mereka berkonsentrasi pada aspek yang lebih canggih.

Inilah prover teorema otomatis online yang berfungsi: http://tryacl2.org/ , yang menunjukkan kesetaraan dengan menemukan urutan perjalanan / asosiasi / distribusi dll:

xy+x+y=x+y(x+1) ?
(thm (= (+ (* x y) x y) (+ x (* y (+ x 1))) ))--- 188 langkah

y+x(y+1)=x+y(x+1) ?
(thm (= (+ y (* x (+ y 1))) (+ x (* y (+ x 1))) ))--- 325 langkah

Ini adalah pertanyaan pertama saya di sini, jadi tolong beri tahu saya jika saya telah memilih tempat yang salah, tag yang salah, cara menggambarkan / bertanya dll. Terima kasih!
NB: pertanyaan ini telah ditulis ulang sebagai tanggapan terhadap komentar
Terima kasih kepada semua responden! Saya sudah belajar banyak.

hyperpallium
sumber
3
Pertanyaan di sini perlu klarifikasi. Bidang apa yang Anda operasikan? Apakah objek seperti " " dan " b " dalam elemen ekspresi Anda dari bidang atau variabel? Apakah ini benar-benar bidang (yaitu, apakah penambahan dan perkalian memiliki invers)? Perhatikan bahwa jumlah-of-produk tidak membantu karena ( a 1 + b 1 ) ( a 2 + b 2 ) ( a n + b n ) memiliki exponetially banyak istilah. ab(a1+b1)(a2+b2)(an+bn)
David Richerby
4
Jika objek adalah variabel, dan pengurangan diizinkan, maka Anda pada dasarnya bertanya tentang pengujian identitas polinomial, yang memiliki algoritma waktu polinomial acak oleh lemma Schwartz-Zippel . iff f ( x ) - g ( x ) = 0 dan ide dasarnya adalah bahwa polinomial yang tidak identik nol tidak memiliki banyak akar jadi, jika Anda mulai menebak akar secara acak dan menemukan banyak akar, ada kemungkinan besar bahwa polinomial Anda identik nol. f(x)=g(x)f(x)g(x)=0
David Richerby
2
Saya terkejut belum ada yang menyebutkan ini, tetapi "jika ada di NP saya tidak perlu khawatir tentang menemukan algoritma polinomial" tidak masuk akal. Setiap masalah dalam P juga dalam NP. Anda mungkin bermaksud bertanya apakah masalahnya NP-complete (atau -hard).
Tom van der Zanden
2
Jika Anda kesulitan dengan dasar-dasarnya, pertanyaan referensi kami mungkin bermanfaat bagi Anda.
Raphael
2
@hyperpallium Sebelum menanyakan apakah suatu bahasa (yaitu masalah keputusan) ada dalam NP, yang terbaik adalah jika Anda mengerti apa artinya ini. Mungkin pertanyaan referensi yang dikaitkan dengan Raphael akan membantu.
Yuval Filmus

Jawaban:

9

Masalah Anda berkurang menjadi nol pengujian polinomial multivarian, yang memiliki algoritma acak yang efisien.

Ekspresi Anda semuanya polinomial multivarian. Rupanya, ekspresi Anda dibangun oleh aturan berikut: (a) jika adalah variabel, maka x adalah ekspresi; (B) jika c adalah konstanta, maka c adalah ekspresi; (c) jika e 1 , e 2 adalah ekspresi, maka e 1 + e 2 dan e 1 e 2 adalah ekspresi. Jika memang itu yang Anda maksudkan, setiap ekspresi adalah polinomial multivarian atas variabel.xxcce1,e2e1+e2e1e2

Sekarang, Anda ingin tahu apakah dua ekspresi setara. Ini sama dengan menguji apakah dua polinomial multivariat setara: diberikan dan p 2 ( x 1 , ... , x n ) , Anda ingin tahu apakah kedua polinomial ini setara. Anda dapat menguji ini dengan mengurangi mereka dan memeriksa apakah hasilnya sama dengan nol: definep1(x1,,xn)p2(x1,,xn)

q(x1,,xn)=p1(x1,,xn)p2(x1,,xn).

Sekarang sama dengan jika dan hanya jika q adalah nol polinomial.p1,p2q

Menguji apakah sama dengan nol adalah masalah pengujian nol untuk polinomial multivarian. Ada algoritma yang efisien untuk itu. Sebagai contoh, salah satu contoh algoritma adalah untuk mengevaluasi q ( x 1 , ... , x n ) pada banyak nilai acak x 1 , ... , x n . Jika Anda menemukan nilai x 1 , ... , x n sedemikian sehingga q ( x 1 , ... , x n ) , maka Anda tahu bahwa qqq(x1,,xn)x1,,xnx1,,xnq(x1,,xn)qtidak identik nol, yaitu, tidak setara. Jika setelah banyak percobaan semuanya nol, maka Anda dapat menyimpulkan bahwa q sama dengan nol (jika q tidak sama dengan nol, probabilitas bahwa semua percobaan tersebut menghasilkan nol dapat dibuat rendah secara eksponensial). Jumlah iterasi yang perlu Anda lakukan terkait dengan tingkat q ; lihat literatur tentang pengujian identitas polinomial untuk detailnya.p1,p2qqq

Misalnya, lihat https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma dan http://rjlipton.wordpress.com/2009/11/30/the-Curious-history-of-the- schwartz-zippel-lemma /

Algoritma ini berlaku jika Anda mengerjakan bidang yang terbatas. Anda tidak menyatakan apa bidang / cincin Anda bekerja di, dan apakah Anda memperlakukan ekspresi ini sebagai ekspresi formal (misal, polinomial sebagai objek abstrak) atau sebagai fungsi dari . Jika Anda mengerjakan bidang yang terbatas, metode di atas berlaku segera.FnF

Jika Anda memperlakukan ekspresi sebagai objek formal, maka ekspresi Anda setara dengan polinomial multivarian dengan koefisien integer. Anda dapat menguji kesetaraan ini dengan memilih besar acak prime dan pengujian kesetaraan modulo r , yaitu, di bidang Z / r Z . Ulangi ini berkali-kali secara polin, dengan nilai acak r yang berbeda , dan Anda harus mendapatkan algoritma acak yang efisien untuk menguji kesetaraan ekspresi formal ini.rrZ/rZr

DW
sumber
1
Di sisi lain, akan sulit untuk membuktikan bahwa untuk setiap ekspresi yang identik-nol, ada bukti yang tidak terlalu lama bahwa ekspresi tersebut identik dengan nol.
@ RickyDemer, poin bagus! Pengamatan yang bagus. Saya menafsirkan pertanyaan sebagai bertanya tentang pengujian kesetaraan daripada membuktikannya, tapi itu pengamatan yang sangat bagus. (Jika Anda ingin menunjukkan bukti kesetaraan dalam praktiknya, saya kira layak untuk menunjukkan bukti tersebut jika Anda bersedia membuat asumsi kriptografi, untuk beberapa definisi "bukti" - misalnya, skema yang mencapai tingkat kesehatan dalam model oracle acak.)
DW
1
Terima kasih! Saya memperlakukan mereka sebagai objek formal, tanpa terbalik, pembagian atau pengurangan (tetapi menggunakan aljabar sekolah tinggi untuk pertanyaan ini; tampaknya lebih mungkin sudah diselesaikan). Apakah yang Anda maksud, terus memilih bilangan prima random besar , dan ini memperlakukan ekspresi seolah-olah mereka bidang terbatas atas set yang mendasari bilangan bulat [ 0 .. r - 1 ] ? Tautan wiki itu mengatakan tidak ada algoritma deterministik sub-eksponensial yang diketahui untuk pengujian-nol ini. Apakah Anda tahu jika itu berlaku untuk masalah saya? r[0..r1]
hyperpallium
1
@ hppallium, ya persis itulah yang saya maksud. Ya, saya percaya itu berlaku untuk masalah Anda juga. Itu sebabnya saya menyarankan algoritma acak - ada algoritma acak yang efisien, meskipun tidak ada algoritma deterministik efisien yang diketahui.
DW
Sebagaimana ditunjukkan dalam komentar di atas, OP tidak bekerja di bidang yang terbatas, melainkan semiring komutatif. Ini berarti bahwa inversi aditif tidak dijamin ada, jadi "kurangi" ekspresi untuk memeriksa kesetaraan dengan nol bukanlah operasi yang valid.
apnorton
0

Untuk menindaklanjuti kendala satu-kekuatan , satu-koefisien dan satu-konstanta dalam pertanyaan:

Ini menentukan subset masalah pengujian identitas polinomial. Jelas, mereka dapat diselesaikan dengan teknik yang memecahkan masalah umum. Pertanyaannya adalah apakah mereka membentuk subset yang lebih mudah dipecahkan.

(a+b)n(a+b)(a+b)=aa+ab+ab+bb=aa+2ab+bb(aa+2ab+bb)(a+b)=aaa+2aab+abb+aab+2abb+bbb=aaa+3aab+3abb+bbb and again terms are combined, making a smaller simpler problem. This combining of terms is a form of dynamic programming.

That is, the possibility of combining terms, creating a non-one coefficient, makes the problem easier not harder.

(Although there is more work in calculation in multiplying non-one coefficients)

non-one constants are included in the above argument by considering constants as variables with zero exponent.

one-power I don't think this makes any difference. Although non-one exponents can be created in more than one way (e.g. a4=a2a2=a1a3), and this can lead to overlap and combination (as in the Binomial Theorm/Pascal's triangle above), actual combination is only possible if non-one coefficients are allowed.

The above is not a formal or rigorous argument. It rests on an assumption about what makes the problem difficult. But it does seem to me that combining terms only makes for an easier problem - so preventing this by the one coefficient constraint is not going to make the subset easier.

hyperpallium
sumber