- masalah lengkap dengan kuasi polinomial terikat pada sejumlah solusi

FewP adalah kelas $NP$ -masalah dengan polinom terikat pada jumlah solusi (dalam ukuran input). Tidak ada dikenal $NP$ masalah -Lengkap di $fewP$ . Saya tertarik pada seberapa jauh kita dapat memperluas pengamatan ini.

Apakah ada alam $NP$ masalah -Lengkap dengan kuasi-polinomial atas terikat pada jumlah solusi (saksi)? Apakah ada dugaan yang diterima secara luas yang akan mengesampingkan kemungkinan seperti itu?

Alami berarti bahwa masalahnya bukan masalah buatan yang dibuat-buat untuk menjawab pertanyaan (atau yang serupa) dan orang-orang tertarik pada masalah secara mandiri (sebagaimana didefinisikan oleh Kaveh).

EDIT: karunia tersebut akan diberikan kepada alam seperti $NP$ masalah -Lengkap atau argumen yang masuk akal mengesampingkan adanya masalah seperti (menggunakan diterima secara luas dugaan kompleksitas-teori).

Motivasi: intuisi saya adalah bahwa $NP$ -completeness Menyebabkan super-polinomial (atau bahkan eksponensial) batas bawah pada jumlah saksi.

Ini pertanyaan yang sangat menarik.

Pertama, komentar klarifikasi. Perhatikan bahwa "batas atas jumlah saksi" bukanlah properti dari masalah komputasi semata, tetapi dari verifier tertentu yang digunakan untuk memutuskan $NP$ , sama seperti "batas atas jumlah negara" tidak akan menjadi milik masalah tetapi dari mesin Turing yang memutuskannya. Jadi mengatakan " N P masalah dengan batas atas jumlah solusi" tidak cukup akurat, dan jika P = N P maka setiap N P masalah memiliki verifier dengan sejumlah solusi yang diinginkan (termasuk nol, dan termasuk semua string mungkin) .$NP$$P = NP$$NP$

Jadi kami harus membuat definisi, untuk menjawab pertanyaan Anda. Untuk s : N → N , katakanlah N P masalah L "memiliki paling s ( n ) solusi" jika untuk beberapa konstan c ada O ( n c ) waktu verifier V seperti itu, untuk setiap panjang input n dan untuk setiap x ∈ L dengan panjang n , ada yang berbeda y 1 , … , y s ( $s : {\mathbb N} \rightarrow {\mathbb N}$$NP$$L$$s(n)$$c$$O(n^c)$$V$$n$$x \in L$$n$) dengan panjang n c sehinggaV(x, y i )menerima untuk semuai, danV(x,y)menolak semuaydengan panjang n c .$y_1,\ldots,y_{s(n)}$$n^c$$V(x,y_i)$$i$$V(x,y)$$y$$n^c$

Yang saya pikir bisa saya katakan saat ini adalah ini:

1. Setiap N P- masalah lengkap yang saya tahu (didefinisikan oleh beberapa verifier alami) memiliki versi penghitungan # P -complete yang jelas (dengan verifier yang sama ).$NP$$\#P$
2. Untuk masalah N P -lengkap yang didefinisikan dengan verifier yang memiliki paling banyak solusi p o l y ( n ) (atau bahkan 2 n o ( 1 ) ) versi penghitungan yang sesuai mungkin bukan # P -lengkap.$NP$$poly(n)$$2^{n^{o(1)}}$$\#P$

Lebih detail: Misalkan L adalah N P -complete, dengan verifier V yang memiliki paling banyak solusi O ( n c ) . Kemudian menghitung "keputusan" versi L , yang kami definisikan sebagai$L$$NP$$V$$O(n^c)$$L$

$Count_L(x) := \text{the number of $y$ such that $V(x,y)$ accepts}$

adalah dihitung di F P N P [ O ( log n ) ] , yaitu, fungsi polytime dengan O ( log n ) query ke N P . Itu karena memutuskan apakah jumlah solusi untuk x paling banyak k adalah dalam N P : saksi, jika ada, hanyalah jumlah y i yang membuat V menerima, yang kita tahu paling banyak O ( n c$FP^{NP[O(\log n)]}$$O(\log n)$$NP$$x$$k$$NP$$y_i$$V$$O(n^c)$. Kemudian kita dapat Binary Search menggunakan ini N P masalah untuk menghitung jumlah pasti solusi untuk L .$NP$$L$

Oleh karena itu, masalah N P -lengkap seperti ini tidak dapat diperluas ke masalah # P -lengkap dengan cara biasa, kecuali # P ⊆ F P N P [ O ( log n ) ] . Ini terlihat tidak mungkin; seluruh hierarki waktu polinomial pada dasarnya akan runtuh ke P N P [ O ( log n ) ] .$NP$$\#P$$\#P \subseteq FP^{NP[O(\log n)]}$$P^{NP[O(\log n)]}$

Jika Anda menganggap s ( n ) = 2 n o ( 1 ) di atas, Anda masih akan mendapatkan konsekuensi yang tidak mungkin. Anda akan menunjukkan bahwa # P dapat dihitung dalam 2 n o ( 1 ) kali dengan oracle N P. Itu lebih dari cukup untuk membuktikan, misalnya, bahwa E X P N P ≠ P P dan selanjutnya E X P N P ⊄ P / p o l $s(n) = 2^{n^{o(1)}}$$\#P$$2^{n^{o(1)}}$$NP$$EXP^{NP} \neq PP$$EXP^{NP} \not\subset P/poly$. Not that those separations are unlikely, but it seems unlikely they'd be proved by giving a subexp time $NP$-oracle algorithm for the Permanent.

By the way, I have said nothing too insightful here. There is almost certainly an argument like this in the literature.