Apakah ada algoritma waktu subeksponensial untuk masalah NP-complete?

51

Apakah ada masalah NP-lengkap yang telah membuktikan algoritma waktu subeksponensial?

Saya meminta input kasus umum, saya tidak berbicara tentang kasus khusus yang dapat ditelusuri di sini.

Dengan sub-eksponensial, maksud saya urutan pertumbuhan di atas polinomial, tetapi kurang dari eksponensial, misalnya . $n^{\log n}$

complexity-theory np-complete np ksb
sumber

10

Apa yang Anda maksud dengan "sub-eksponensial"? Jika yang Anda maksud

, jawabannya pasti ya. Jika maksud Anda

, saya yakin jawabannya tidak.

2^{o (n)}

$2^{o(n)}$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

JeffE

57

Tergantung pada apa yang Anda maksudkan dengan subeksponensial. Di bawah ini saya jelaskan beberapa arti "subeksponensial" dan apa yang terjadi dalam setiap kasus. Setiap kelas ini terkandung dalam kelas-kelas di bawahnya.

I. $2^{n^{o(1)}}$

Jika dengan subexpoential yang Anda maksud adalah , maka dugaan dalam teori kompleksitas yang disebut ETH (Exponential Time Hypothesis) menyiratkan bahwa tidak ada masalah -hard yang dapat memiliki algoritma dengan running-time . $2^{n^{o(1)}}$ $\mathsf{NP}$ $2^{n^{o(1)}}$

Perhatikan bahwa kelas ini ditutup dalam komposisi dengan polinomial. Jika kami memiliki algoritme waktu subeksponensial untuk masalah -apa pun , kami dapat menggabungkannya dengan pengurangan waktu polinomial dari SAT untuk mendapatkan algoritma subeksponensial untuk 3SAT yang akan melanggar ETH. $\mathsf{NP}$

II , yaitu untuk semua $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

Situasinya mirip dengan yang sebelumnya.

Hal ini tertutup di bawah polinomial sehingga tidak ada masalah -Hard dapat diselesaikan dalam waktu ini tanpa melanggar ETH. $\mathsf{NP}$

AKU AKU AKU. , yaitu untuk beberapa $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

Jika dengan subeksponensial yang Anda maksud adalah untuk beberapa maka jawabannya adalah ya, ada masalah yang terbukti. $2^{O(n^\epsilon)}$ $\epsilon<1$

Ambil - masalah lengkap seperti SAT. Ini memiliki algoritma brute-force yang berjalan dalam waktu . Sekarang mempertimbangkan versi empuk dari SAT dengan menambahkan string ukuran ke input: $\mathsf{NP}$ $2^{O(n)}$ $n^k$

S A T^{'} = {⟨ φ, w ⟩ ∣ φ \in S A T and | w | = | φ |^{k}}

$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$

Sekarang masalah ini adalah -hard dan dapat diselesaikan dalam waktu $\mathsf{NP}$ . $2^{O(n^\frac{1}{k})}$

IV. $2^{o(n)}$

Ini berisi kelas sebelumnya, jawabannya mirip.

V. , yaitu untuk semua $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

Ini berisi kelas sebelumnya, jawabannya mirip.

VI. , yaitu untuk beberapa $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$

Ini berisi kelas sebelumnya, jawabannya mirip.

Apa artinya subeksponensial?

"Di atas polinomial" bukan batas atas tetapi batas bawah dan disebut sebagai superpolinomial .

Fungsi seperti disebut quasipolynomial , dan seperti yang ditunjukkan namanya hampir polinomial dan jauh dari eksponensial, subeksponensial biasanya digunakan untuk merujuk kelas fungsi yang jauh lebih besar dengan tingkat pertumbuhan yang jauh lebih cepat. $n^{\lg n}$

Seperti namanya, "subeksponensial" berarti lebih lambat daripada eksponensial . Dengan eksponensial kita fungsi biasanya berarti di kelas , atau di kelas yang lebih bagus (yang ditutup di bawah komposisi dengan polinomial). $2^{\Theta(n)}$ $2^{n^{\Theta(1)}}$

Subeksponetial harus dekat dengan ini tetapi lebih kecil. Ada berbagai cara untuk melakukan ini dan tidak ada makna standar. Kita dapat mengganti dengan dalam dua definisi eksponensial dan memperoleh I dan IV. Hal yang baik tentang mereka adalah bahwa mereka didefinisikan secara seragam (tidak ada penjumlah lebih dari ). Kita dapat mengganti dengan koefisien multiplikasi untuk semua , kita mendapatkan II dan V. Mereka dekat dengan I dan IV tetapi tidak terdefinisikan secara seragam. Opsi terakhir adalah mengganti dengan konstanta multiplikasi untuk beberapa . Ini memberi II dan VI. $\Theta$ $o$ $\epsilon$ $\Theta$ $\epsilon$ $\epsilon>0$ $\Theta$ $\epsilon$ $\epsilon<1$

Yang mana harus disebut subeksponensial diperdebatkan. Biasanya orang menggunakan yang mereka butuhkan dalam pekerjaan mereka dan menyebutnya sebagai subeksponensial.

Saya adalah preferensi pribadi saya, ini kelas yang bagus: ditutup dengan komposisi dengan polinomial dan didefinisikan secara seragam. Hal ini mirip dengan yang menggunakan . $\mathsf{Exp}$ $2^{n^{O(1)}}$

II sepertinya digunakan dalam definisi kelas kompleksitas . $\mathsf{SubExp}$

III digunakan untuk batas atas algoritmik, seperti yang disebutkan dalam jawaban Pal.

IV juga umum.

V digunakan untuk menyatakan dugaan ETH.

$\mathsf{L}$ $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{PSpace}$ $\mathsf{Exp}$

Musim panas

$\mathsf{NP}$

Kaveh
sumber

7

Jawaban ini harus masuk ke Wikipedia.

Erel Segal-Halevi

32

$2^{O(\sqrt{n} \log n)}n^{O(1)}$ $2^{O(\sqrt{n})}n^{O(1)}$

Umpan Balik Arc Set pada Turnamen [Noga Alon, Daniel Lokshtanov, Saket Saurabh, ALP 2009]
Pengisian Minimum dan Penyelesaian Rantai [Fomin and Villanger SODA 2012]
Penghapusan Tepi Tepi [Ghosh et al SWAT 2012]
$t$
Banyak masalah bidimensionalitas, masalah grafik berbeda pada grafik genus terikat dan terutama grafik planar (lihat Demaine, Fomin, Hajiaghayi, Thilikos: Algoritma parameterized subeksponensial pada grafik gen-gen terikat dan H-minor-bebas )
Algoritma Parameter-Waktu Subeksponensial untuk Steiner Tree pada Grafik Planar [Pilipczuk et al STACS 2013]
Penyelesaian Sempurna Trivially, Penyelesaian Ambang Batas dan Penyempurnaan Pseudosplit [D. et al STACS 2014]
Penyelesaian Interval [Bliznets et al]
Penyelesaian Interval yang Tepat [Bliznets et al]

Pål GD
sumber

1

2^{O (n^{ϵ})}

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

ϵ < 1

$\epsilon<1$

2^{n^{o (1)}}

$2^{n^{o(1)}}$

Apakah ada algoritma waktu subeksponensial untuk masalah NP-complete?

Jawaban:

I. 2no ( 1 )2no(1)2^{n^{o(1)}}

II , yaitu 2 O ( n ϵ ) untuk semua 0 < ϵ⋂0 < ϵ2O ( nϵ)⋂0<ϵ2O(nϵ)\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}2O(nϵ)2O(nϵ)2^{O(n^\epsilon)} 0<ϵ0<ϵ0 < \epsilon

AKU AKU AKU. , yaitu 2 O ( n ϵ ) untuk beberapa ϵ < 1⋃ϵ<12O(nϵ)⋃ϵ<12O(nϵ)\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}2O(nϵ)2O(nϵ)2^{O(n^\epsilon)} ϵ<1ϵ<1\epsilon < 1

IV. 2o ( n )2o(n)2^{o(n)}

V. , yaitu 2 ϵ n untuk semua ϵ > 0⋂0 < ϵ2ϵ n⋂0<ϵ2ϵn\bigcap_{0 < \epsilon}2^{\epsilon n}2ϵ n2ϵn2^{\epsilon n} ϵ > 0ϵ>0\epsilon>0

VI. , yaitu 2 ϵ n untuk beberapa ϵ < 1⋃ϵ < 12ϵ n⋃ϵ<12ϵn\bigcup_{\epsilon < 1}2^{\epsilon n}2ϵ n2ϵn2^{\epsilon n} ϵ < 1ϵ<1\epsilon<1

Apa artinya subeksponensial?

I. $2^{n^{o(1)}}$

II , yaitu untuk semua $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $0 < \epsilon$

AKU AKU AKU. , yaitu untuk beberapa $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$ $2^{O(n^\epsilon)}$ $\epsilon < 1$

IV. $2^{o(n)}$

V. , yaitu untuk semua $\bigcap_{0 < \epsilon}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon>0$

VI. , yaitu untuk beberapa $\bigcup_{\epsilon < 1}2^{\epsilon n}$ $2^{\epsilon n}$ $\epsilon<1$