Perkiraan waktu subeksponental

Ada studi tentang algoritma perkiraan untuk masalah lengkap NP dalam waktu Polinomial dan algoritma yang tepat dalam waktu eksponensial. Apakah ada studi tentang algoritma perkiraan untuk masalah lengkap NP dalam waktu subeksponensial dari formulir mana ? $2^{n^{\delta_2}}$ $\delta_2\in(0,1)$

Saya terutama tertarik pada apa yang diketahui tentang masalah waktu yang sulit diperkirakan jumlahnya polinomial seperti nomor Kemerdekaan dan nomor Clique dalam waktu subeksponensial? Perhatikan bahwa ETH hanya melarang perhitungan yang tepat dalam jangka waktu seperti itu. Katakanlah angka Kemerdekaan adalah pada grafik dengan jumlah simpul untuk beberapa . Apakah skema perkiraan faktor mungkin untuk angka Kemerdekaan dalam waktu mana dan adalah beberapa real positif yang diperbaiki? $\alpha(G)=2^{r(n)n}$ $|V|=2^{s(n)n}$ $0<r(n)<s(n)$ $2^{(r(n)n)^{\delta_1}}$ $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ $0<\delta_1<1$ $0<\delta_2<1$

Itu untuk setiap apakah ada sehingga dapat diperkirakan dalam faktor waktu ? $\delta_1\in(0,1)$ $\delta_2\in (0,1)$ $\alpha(G)$ $2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$

approximation-algorithms approximation-hardness T ....
sumber

apakah Anda benar-benar bermaksud meminta waktu menjalankan sublinear di nomor independen?

Sasho Nikolov

Tidak, waktu yang berjalan adalah sub-eksponensial. Sepenuhnya eksponensial adalah . Di sini waktu berjalan adalah dari bentuk dan di sini .

2^{| V |}

$2^{|V|}$

2^{| V |^{δ_{1}}}

$2^{|V|^{\delta_1}}$

α (G) = 2^{r (n) n} = | V |^{\frac{r (n)}{s (n)}} < | V | = 2^{s (n) n}

$\alpha(G)=2^{r(n)n}=|V|^{\frac{r(n)}{s(n)}}<|V|=2^{s(n)n}$

T ....

Seharusnya

δ_{2}

$\delta_2$ dalam komentar sebelumnya dan kami memiliki .

α (G) < | V | < 2^{| V |^{δ_{2}}} < 2^{| V |}

$\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$

T ....

Saya pikir saya punya kesalahan ketik sebelumnya.

T ....

Apakah Sudah Jelas Sekarang?

T ....

Jawaban:

Satu makalah yang memberikan jawaban untuk pertanyaan ini adalah Chalermsook, Laekhanukit, & Nanongkai (2013) .

Ada juga karya terkait dalam konteks Traktabilitas Parameter Tetap seperti Hajiaghayi, Khandekar, & Kortsarz (2013) dan Chitnis, Hajiaghayi, Kortsarz (2013) . Hasil kekerasan ini dibuktikan dengan berbagai asumsi seperti ETH atau keberadaan PCP yang sangat kuat.

Igor Shinkar
sumber

arxiv.org/pdf/1308.2617v2.pdf mengatakan "Untuk setiap

lebih besar dari konstanta, algoritma

aproximation untuk masalah set independen maksimum harus dijalankan dalam waktu setidaknya

. Ini hampir cocok dengan batas atas

". Jadi rasio aproksimasi

dapat dicapai dalam

r

$r$

r

$r$

2^{n^{1 - ϵ} / r^{1 + ϵ}}

$2^{{n^{1-\epsilon}}/{r^{1+\epsilon}}}$

2^{n / r}

$2^{n/r}$

r = 2^{(s (n) n)^{δ_{1}}}

$r=2^{({s(n)n})^{\delta_1}}$

2^{2^{r (n) n - (s (n) n)^{δ_{1}}}} = 2^{2^{1 - \frac{(s (n) n)^{δ_{1}}}{r (n) n} r (n) n}} = 2^{2^{δ_{2} r (n) n}}

$2^{2^{r(n)n - ({s(n)n})^{\delta_1}}} = 2^{2^{1 - \frac{({s(n)n})^{\delta_1}}{r(n)n}r(n)n}}=2^{2^{\delta_2 r(n)n}}$

δ_{2} > 1 - \frac{(s (n))^{δ_{1}} n^{δ_{1} - 1}}{r (n)}

$\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$ ?

T....

You have many $FPA$ (fixed parameter approximation) algorithms for which a sublinear parameter translates into subexponential time in the length of the input.

For example, approximating the number of simple paths of length $k$ , for some $k=n^c$ (where $c<1$ ), gives you a running time of:

$O((2e)^{n^c}\cdot 2^{polylog(n)})$ .

R B
sumber