Obstruksi seperti ETH

Kita tahu di bawah kita tidak bisa menyelesaikan -SUM dalam waktu bawah fungsi apa pun (biasanya ). $ETH$ $K$ $f(K)poly(nK)$ $f(K)$ $2^{O(K)}$

Apakah ada dugaan yang mencegah kompleksitas $(\log n)^{O(K)}$ (ini sepenuhnya konsisten dengan kemungkinan karena $K=\Omega(n)$ kita memerlukan waktu eksponensial untuk jumlah himpunan bagian) atau apakah kemungkinan seperti itu diperbolehkan?

cc.complexity-theory subset-sum T ....
sumber

Jawaban:

ETH sendiri menghalangi kemungkinan ini.

Dalam https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf kami menunjukkan bahwa setiap $n^{O(1)} n^{k/\alpha(k)}$ algoritma waktu untuk k-SUM, untuk monoton setiap nondecreasing tak terbatas fungsi $\alpha$ , akan menyiratkan ETH salah.

Ryan Williams
sumber

Apakah maksud Anda bahwa

benar-benar meningkat, atau setidaknya pergi hingga tak terbatas?

α

$\alpha$

Sasho Nikolov

@RyanWilliams Mirip semangat untuk ETH seperti obstruksi. Apakah ada sesuatu yang akan mencegah kompleksitas

dengan saran ukuran polinomial atau oracle PPAD?

O ((\log n)^{O (k)})

$O((\log n)^{O(k)})$

T ....

Menambahkan "tidak terikat" :)

Ryan Williams

@Brout Perhatikan bahwa (log (n)) ^ k adalah fungsi FPT, jadi ya, aturan ETH yang keluar. Dengan saran ukuran poli itu berarti sirkuit ukuran subeksponensial untuk 3sat. Dengan peramalan PPAD tampaknya menyiratkan bahwa ETH menyiratkan PPAD tidak dalam P. Bagi saya itu akan menjadi terobosan, saya tidak tahu banyak bukti yang menguatkan bahwa PPAD tidak dalam P

Ryan Williams