Masalah mudah dengan versi penghitungan yang sulit

20

Wikipedia memberikan contoh masalah di mana versi penghitungannya sulit, sedangkan versi keputusannya mudah. Beberapa di antaranya menghitung kecocokan sempurna, menghitung jumlah solusi untuk -SAT dan jumlah penyortiran topologi. $2$

Apakah ada kelas penting lainnya (misalnya contoh dalam kisi, pohon, teori bilangan dan sebagainya)? Apakah ada ringkasan masalah seperti itu?

Ada banyak jenis masalah dalam yang memiliki versi penghitungan yang sulit. $P$ $\#P$

Apakah ada versi masalah alami dalam yang lebih sepenuhnya dipahami atau lebih sederhana daripada pencocokan sempurna bipartit umum (harap sertakan detail mengapa lebih sederhana seperti terbukti di kelas terendah dari hierarki dan sebagainya) di beberapa area lainnya (seperti teori bilangan, kisi-kisi) atau paling tidak untuk grafik bipartit sederhana tertentu, yang versi hitungnya ? $P$ $NC$ $\#P$

Contoh dari kisi, polytopes, penghitungan titik, teori bilangan akan dihargai .

reference-request counting-complexity nt.number-theory permanent decision-trees T ....
sumber

1

Mungkin Anda menginginkan masalah alami , karena [dengan pengurangan dari #SAT, masalah yang # P-hard di bawah [reduksi yang mengalikan jawaban dengan angka bukan nol] memiliki masalah keputusan sulit-HP] dan [oleh fungsi identitas, {x: x adalah 1+ (number_of_variables_ ( )) satu atau [nol diikuti oleh penugasan yang memuaskan ke ]} adalah # P-hard di bawah tipe pengurangan berikutnya yang paling ketat, tetapi versi keputusannya sepele].

ϕ

$\phi$

ϕ

$\phi$

@ RickyDemer tulisan Anda ringkas. Ya saya ingin masalah alami.

T ....

Apakah kita benar-benar tidak sepenuhnya memahami pencocokan sempurna dalam grafik bipartit? Juga, ada algoritma RNC2 untuk masalah tersebut.

Sasho Nikolov

1

Ya kami tidak. Kami tidak memiliki algoritme deterministik .

N C

$NC$

T ....

8

Inilah contoh yang sangat bagus (saya mungkin bias).

Diberikan seperangkat yang dipesan sebagian:
a) apakah ia memiliki ekstensi linier (yaitu, pesanan total yang kompatibel dengan pesanan parsial)? Sepele: Semua poset memiliki setidaknya satu ekstensi linier
b) Berapa banyak yang dimilikinya? # P-lengkapi untuk menentukan ini (Brightwell dan Winkler, Counting Linear Extensions , Order, 1991)
c) Bisakah kita menghasilkan semuanya dengan cepat? Ya, dalam waktu diamortisasi konstan (Pruesse dan Ruskey, Menghasilkan Ekstensi Linear Cepat , SIAM J Comp 1994)

Gara Pruesse
sumber

3

+1: Saya setuju itu adalah contoh yang sangat bagus (berpikir untuk mempostingnya sendiri dan kemudian melihat jawaban ini). Juga, jangan sampai seseorang berkata "Bagaimana kalau memutuskan apakah ada setidaknya satu ekstensi linear lainnya ", masalah itu juga sangat sepele: total order memiliki 1 ekstensi, semua poset lainnya memiliki> 1. Dan mendeteksi dengan tepat 2 ekstensi juga mudah (ini terjadi jika ada tepat sepasang elemen yang tak tertandingi). Bahkan, ada klasifikasi lengkap dari poset dengan hingga 7 ekstensi linear (lihat Hanamura-Iwata, IPL 2011 ).

Joshua Grochow

Ini memang contoh yang bagus. Namun ada banyak masalah "sederhana" yang menikmati jenis properti yang sama (lebih sederhana dalam arti bahwa properti ini hampir sepele untuk dibuktikan). Menghitung jumlah penugasan yang memuaskan dari DNF: a) setiap DNF yang tidak kosong memuaskan b) penghitungan adalah # P-selesai (reduksi ke #SAT) c) pencacahan dapat dilakukan dengan penundaan polinomial (waktu diamortisasi yang mungkin konstan, miliki untuk memikirkannya)

holf

Saya akan sangat tertarik mengetahui apakah tugas memuaskan DNF dapat dihasilkan dalam waktu diamortisasi konstan (CAT). Pada saat itu dan tulisan saya dengan Frank, pada tahun 1994, ekstensi linier adalah objek "terdefinisi secara alami" pertama yang penghitungannya sulit dan pembangkitannya secepat yang didapat, ketika diamortisasi (yaitu, CAT). Solusi DNF sepertinya juga kandidat untuk hal ini. Adakah yang punya referensi?

Gara Pruesse

@ GaraPruesse Saya tidak punya referensi untuk itu. Untuk monoton-DNF, itu setara dengan menghitung set himpunan hypergraphs dan beberapa teknik untuk meningkatkan penundaan disajikan dalam "Algoritme yang efisien untuk menggandakan hipergraf skala besar" oleh Keisuke Murakami dan Takeaki Uno dl.acm.org/citation.cfm? id = 2611867 . Kita harus memeriksa apakah itu memberi CAT. Untuk DNF, intuisi saya adalah bahwa jika ada klausa kecil maka Anda sudah memiliki solusi yang cukup untuk memaksa kasar. Jika tidak, Anda hanya memiliki klausa besar dan yang kemudian lebih cenderung berbenturan dan yang dapat digunakan untuk merancang algoritma CAT.

Serigala

17

Salah satu contoh menarik dari teori bilangan adalah menyatakan bilangan bulat positif sebagai jumlah empat kotak. Ini dapat dilakukan dengan relatif mudah dalam waktu polinomial acak (lihat artikel 1986 saya dengan Rabin di https://dx.doi.org/10.1002%2Fcpa.3160390713 ), dan jika saya ingat dengan benar, sekarang bahkan ada polinomial deterministik-waktu larutan. Tetapi menghitung jumlah representasi seperti itu akan memungkinkan Anda untuk menghitung fungsi jumlah pembagi , yang merupakan waktu polinomial acak yang setara dengan anjak piutang . Jadi masalah penghitungan mungkin sulit. $\sigma(n)$ $n$

Jeffrey Shallit
sumber

"Jadi masalah penghitungan mungkin sulit" maksudmu mungkin

keras? apakah kamu punya bukti?

# P

$\#P$

T ....

Dengan "mungkin sulit" Maksud saya adalah polinomial-waktu acak setara dengan faktorisasi bilangan bulat.

Jeffrey Shallit

3

Jadi, untuk membuatnya eksplisit: masalahnya bukan # P-hard (kecuali semua neraka longgar).

Emil Jeřábek mendukung Monica

@ JeffreyShallit Apakah ada contoh

?

# P

$\#P$

T ....

Saya pikir berikut ini adalah contoh yang lebih sederhana: "Apakah

memiliki lebih besar pembagi yang tepat dari

" vs "Berapa banyak pembagi yang tepat lebih besar dari

tidak

miliki?". Versi keputusan sama dengan "

adalah komposit" sehingga dalam

, tetapi versi penghitungan tidak terlihat lebih mudah daripada memfaktorkan.

n

$n$

1

$1$

1

$1$

n

$n$

n

$n$

P

$P$

Dan Brumleve

17

Contoh yang sangat bagus dan sederhana dari Graph Theory adalah menghitung jumlah sirkuit Eularian dalam grafik yang tidak terarah.

Versi keputusannya mudah (... dan masalah Seven Bridges of Königsberg tidak memiliki solusi :-)

Versi penghitungannya adalah # P-hard: Graham R. Brightwell, Peter Winkler: Menghitung Sirkuit Euler adalah # P-Lengkap . ALENEX / ANALCO 2005: 259-262

Marzio De Biasi
sumber

Makalah itu "Pendekatan kami adalah untuk menunjukkan bahwa, dengan bantuan oracle yang menghitung sirkuit Euler, mesin Turing dapat ... dan" Kami ingin menghitung jumlah

orientasi Euler dari

. "ayat-break 'Kami membangun untuk setiap prima ganjil

, grafik

jumlah yang dari bola setara dengan

modulo

.' dan" Kami ulangi proses ini untuk setiap p prima antara

dan

, di mana

, dan ... "tentu menyarankan bahwa mereka hanya memberikan reduksi paralel, bahkan bukan

N

$N$

G

$G$

p

$p$

G_{p}

$G_p$

N

$N$

p

$p$

m

$m$

m^{2}

$m^2$

| E | = m

$|E| = m$

-pengurangan kueri.

m^{ϵ}

$m^{\epsilon}$

@MarzioDeBiasi adalah keputusan sirkuit Euler di NC?

T ....

1

@ AJ. Anda hanya perlu menghitung paritas derajat setiap node dan memeriksa semuanya. Tampaknya berada di NC.

Sasho Nikolov

4

Anda dapat mengambil paritas

bit menggunakan rumus ukuran

atau sirkuit ukuran linear kedalaman

. Jadi, jika grafik Anda diberikan sebagai matriks adjacency, hitung paritas dari setiap baris, negasikan, dan ambil sebuah AND. DAN dari

bit dapat dilakukan dengan ukuran rumus linear, sehingga secara keseluruhan, Anda mendapatkan

ukuran Boolean rumus dan

ukuran sirkuit Boolean kedalaman

n

$n$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$

n

$n$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

O (\log n)

$O(\log n)$ (atas dasar AND-OR). Jadi masalahnya sebenarnya di

.

{N C}^{1}

$\mathsf{NC}^1$

Sasho Nikolov

2

Faktanya, masalahnya ada di

.

{A C}^{0} [2]

$\mathrm{AC}^0[2]$

Emil Jeřábek mendukung Monica

6

Mengenai pertanyaan kedua Anda, masalah-masalah seperti Monoton-2-SAT (memutuskan kepuasaan formula-CNF memiliki paling banyak 2 literal positif berdasarkan klausa) benar-benar sepele (Anda hanya perlu memeriksa apakah formula Anda kosong atau tidak) tetapi masalah penghitungannya adalah # P-hard. Bahkan perkiraan jumlah penugasan yang memuaskan dari formula semacam itu sulit (lihat On hardness of approximate reasoning, Dan Roth, Artificial Intelligence, 1996).

serigala
sumber

5

Dari [Kayal, CCC 2009] : Secara eksplisit mengevaluasi pemusnahan polinomial di beberapa titik

Dari abstrak: `` Ini adalah satu-satunya masalah komputasi alami di mana menentukan keberadaan suatu objek (polinomial pemusnahan dalam kasus kami) dapat dilakukan secara efisien tetapi perhitungan aktual dari objek tersebut terbukti sulit. ''

Mari menjadi bidang dan menjadi satu set -banyak degree- -variate polinomial atas Sebuah -annihilating polinomial yaitu apapun (non-sepele) st $\mathbb{F}$ $\vec{f} = (f_1, ..., f_k)\in\mathbb{F}[x_1, ..., x_n]$ $k$ $d$ $n$ $\mathbb{F}.$ $\vec{f}$ $A$ $A(f_1, ..., f_k) = 0.$

Keputusan mudah: Selama setiap bidang, dan untuk setiap polinomial - jika ada yang menghancurkan seperti untuk . ((Melalui argumen penghitungan dimensi.)) $k$ $(f_1, ..., f_k)$ $k \ge n+1,$ $A$ $(f_1, ..., f_k)$

Menghitung sulit: Tentukan memusnahkan-Tarahan sebagai masalah fungsional mengevaluasi polinomial yang menghancurkan pada beberapa titik : Mengingat perdana dan satu set yang memiliki minimal monic yang menghancurkan $p,$ $(f_1, ..., f_k)\in\mathbb{Z}[x_1, ..., x_n]$ output bilangan bulat $A(t_1, ..., t_k)\in\mathbb{Z}[t_1, ..., t_k],$ $A(0, ..., 0)\bmod{p}.$

ANNIHILATING-EVAL adalah -hard. Selain itu, yang menghancurkan polinomial tidak memiliki representasi sirkuit kecil kecuali runtuh. $\#\mathsf{P}$ $A(t_1, ..., t_k)$ $\mathsf{PH}$

Daniel Apon
sumber

1

Seperti untuk contoh Marzio, bukti kertas klaim 15.2 tampaknya menunjukkan bahwa mereka hanya menunjukkan kekerasan di bawah pengurangan paralel, daripada bahkan di bawah

-pengurangan kueri.

m^{ϵ}

$m^{\hspace{.02 in}\epsilon}$

1

Sumber daya yang saya dapat temukan semuanya tampaknya tidak setuju dengan definisi. Biarkan AE menjadi masalah yang dibahas oleh jawaban Anda. (... lanjutan)

1

(lanjutan ...) saya belum mencoba untuk bekerja tahu lebih tepat apa dasar-kelas yang mereka gunakan, tapi akan cukup terkejut jika hasilnya mereka lebih baik dari #P =

(

$\big(\hspace{-0.07 in}$ DLOGTIME-seragam TC

^{0}

$^0$

)

$\hspace{-0.06 in}\big)$

^{| |}

$^{\hspace{-0.06 in}||\hspace{-0.06 in}}$

^{AE}

$^{\text{AE}}$

^{[\sqrt{n}]}

$^{\hspace{-0.05 in}[\sqrt{n}]}$ . (... lanjutan)

1

(lanjutan ...) Sejauh yang saya lihat, itu tidak mengikuti LWPP

MP

\subseteq

$\subseteq$

^{AE}

$^{\text{AE}}$

^{[\sqrt[3]{n}]}

$^{[\sqrt[3]{n}]}$

/

$\hspace{-0.06 in}\big/\hspace{-0.04 in}$ poli .

1

Lebih umum, yaitu untuk arbitrary

(bahkan kurang dari

), keputusan itu mudah karena kriteria Jacobian, kan? (Perhatikan bahwa kriteria Jacobian hanya bekerja di karakteristik>

; di karakteristik positif kecil, ada kriteria Jacobian dimodifikasi karena Mittman-Saxena-Scheiblechner , tapi itu ternyata hanya mengarah ke

algoritme untuk keputusan ...)

k

$k$

n

$n$

m a x d e g f_{i}

$max deg f_i$

{N P}^{# P}

$\mathsf{NP}^{\mathsf{\# P}}$

Joshua Grochow

Masalah mudah dengan versi penghitungan yang sulit

Jawaban: