Hasil kondisional menyiratkan kesulitan meningkatkan batas atas / bawah untuk permanen

Biarkan menjadi matriks persegi yang diberikan. Apakah ada bukti bahwa mengalahkan batas bawah kuadratik untuk B sehingga det ( B ) = per ( A ) bisa sulit?$A$$B$$\text{det}(B) = \text{per}(A)$

Adakah dugaan masuk akal yang menyiratkan bahwa membuktikan batas bawah itu sulit? Adakah bukti yang membuktikan bahwa baris (atau kolom) pada batas bawah untuk beberapa ϵ > 0 sulit (misalnya setara dengan V P ≠ V N P )?$\Omega(n^{2+\epsilon})$$\epsilon > 0$$\mathsf{VP} \ne \mathsf{VNP}$

Adakah dugaan masuk akal yang menyiratkan bahwa membuktikan batas atas itu sulit? Adakah bukti yang membuktikan bahwa batas atas untuk beberapa ϵ ∈ ( 0 , 1 ) sulit?$O(2^{n^\epsilon})$$\epsilon \in (0,1)$

$O(2^{n^{\epsilon}})$ $\epsilon<1$

Holger Dell, Thore Husfeldt, dan Martin Wahlén .

Kompleksitas waktu eksponensial dari polinomial permanen dan Tutte.

Makalah lengkap di ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

$n\times n$$O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$

1. Ubah instance 3SAT menjadi permanen seperti pada kertas di atas

2. Ubah permanen menjadi penentu atas matriks yang lebih besar

3. Hitung determinan untuk menemukan jumlah solusi untuk instance 3SAT asli.

$n$$O(2^{n^{\epsilon'}})$$\epsilon'<1$$\epsilon$