Algoritma mengejutkan untuk menghitung masalah

54

Ada beberapa masalah penghitungan yang melibatkan penghitungan banyak hal secara eksponensial (relatif terhadap ukuran input), namun memiliki algoritma deterministik tepat waktu polinomial waktu yang mengejutkan. Contohnya termasuk:

Menghitung kecocokan sempurna dalam grafik planar ( algoritma FKT ), yang merupakan dasar untuk bagaimana algoritma holografik bekerja.
Menghitung rentang pohon dalam grafik (melalui teorema pohon matriks Kirchhoff ).

Langkah kunci dalam kedua contoh ini adalah mengurangi masalah penghitungan untuk menghitung faktor penentu dari matriks tertentu. Penentu itu sendiri, tentu saja, sejumlah banyak hal secara eksponensial, namun secara mengejutkan dapat dihitung dalam waktu polinomial.

Pertanyaan saya adalah: apakah ada algoritma "pasti sangat efisien" tepat dan deterministik yang dikenal untuk menghitung masalah yang tidak mengurangi menghitung komputasi faktor penentu?

cc.complexity-theory counting-complexity big-picture Ashley Montanaro
sumber

8

BTW, lebih banyak masalah penghitungan berkurang untuk menghitung faktor penentu. Penentu integer lengkap untuk kelas GapL, yang berisi #L.

5501

11

Saya tidak tahu apakah masalah berikut ini mengurangi atau tidak menghitung determinan, tetapi saya tetap akan mendaftar:

$v_0$ $v_f$ $v_f$ $v_0$

2) Menghitung jumlah solusi masalah yang dapat didefinisikan dalam logika MSO dalam struktur lebar Pohon yang dibatasi. Lihat misalnya makalah yang memuat karya Courcelle, Arnborg dan lainnya .

$f:\{0,1\}^{n}\rightarrow \{0,1\}$ $x$ $f(x)=1$ $U_f$ $|x\rangle|0\rangle$ $|x\rangle|f(x)\rangle$ $|1\rangle$ $U_fH^{\otimes n}|0\rangle|0\rangle$

Mateus de Oliveira Oliveira
sumber

Terima kasih - item (2) dan (3) menarik tetapi entah bagaimana tidak cukup apa yang saya cari; menghitung masalah dengan lebar pohon dibatasi tampak lebih seperti kasus khusus di mana struktur yang Anda kerjakan sebenarnya dibatasi secara polinomi. Saya lebih tertarik pada kasus-kasus di mana ada "benar-benar" secara eksponensial banyak objek untuk dihitung, tetapi entah bagaimana secara ajaib dapat dihitung dalam waktu polinomial.

Ashley Montanaro

Bukankah itu berarti bahwa, jika Anda menggunakan pengkodean unary, algoritma perlu waktu eksponensial hanya untuk menulis nomornya? Apakah mungkin masalah ini diatasi dengan menggunakan pengkodean biner, tetapi ini terdengar berlawanan dengan saya.

Antonio Valerio Miceli-Barone

2

@ Miceli-Barone, Apa yang Anda katakan akan berlaku untuk hampir semua algoritma waktu poli yang menghasilkan angka. Penentu itu sendiri akan agak besar dalam kasus terburuk di unary.

Raphael

\frac{(n + 1)^{\frac{n + 1}{2}}}{2^{n}}

$\frac{(n + 1)^{\frac{n+1}{2}}}{2^n}$

11

Menghitung jumlah titik-titik kisi dalam polytope rasional (ketika dimensi konstan) dalam waktu polinomial , karena Alexander Barvinok.

Yoshio Okamoto
sumber

2

apa teknik utamanya?

Suresh Venkat

2

Fungsi penghasil singkat. Artikel ekspositori berikut ini akan memberi kami lebih banyak ide. arxiv.org/abs/math/0506466

Yoshio Okamoto

11

Dalam kerangka kerja Holant, ada beberapa kasus yang dapat ditelusuri (untuk alasan non-sepele) selain melalui korek api dalam grafik planar.

1) Fibonacci Gates

2) Setiap set tanda tangan affine .

3) #CSP tertimbang non-negatif

... untuk beberapa nama.

Juga, Teorema TERBAIK memberikan algoritma waktu polinomial untuk menghitung jumlah sirkuit Euler dalam grafik terarah, meskipun bagian dari algoritma tersebut menggunakan perhitungan determinan.

Tyson Williams
sumber

Algoritma mengejutkan untuk menghitung masalah

Jawaban: