Masalah NP-Complete mana yang memiliki algoritma paling cepat diketahui?

Dalam hal runtime asimptotik kasus terburuk, masalah NP-lengkap mana yang memiliki algoritma (paling tepat) paling cepat diketahui dan apa algoritma itu? Adakah yang diketahui lebih cepat dari ? $O(n^2*2^n)$

algorithms reference-request np-complete Wuschelbeutel Kartoffelhuhn
sumber

Algoritma apa yang menjalankan waktu ? EDIT: Saya berasumsi maksud Anda algoritma Held-Karp untuk Traveling Salesman.

O (n^{2} \cdot 2^{n})

$O(n^2 \cdot 2^n)$

Guildenstern

Anda dapat melihat jawaban atas pertanyaan Apakah ada algoritma waktu subeksponensial untuk masalah NP-complete? .

Pål GD

"Lebih cepat dari " tidak masuk akal. Maksudmu ? Atau pertanyaan, "Apakah ada algoritma dengan batas runtime atas yang terbukti lebih baik daripada ?"

O (_)

$O(\_)$

Θ

$\Theta$

O (_)

$O(\_)$

Raphael

Yang terakhir. Ini poin yang valid; mungkin ada algoritma A yang lebih cepat daripada B dalam praktiknya tetapi tidak dengan batas atas yang lebih ketat. Saya tidak yakin mengapa tidak masuk akal untuk mengatakan "lebih cepat dari batas atas" daripada "lebih cepat dari batas bawah DAN atas" ...

Wuschelbeutel Kartoffelhuhn

Jawaban:

Vertex Cover memiliki algoritma yang berjalan dalam waktu , dan karenanya lebih cepat dari , bahkan dengan . Anda dapat melihat Daftar ras FPT untuk daftar singkat waktu FPT berjalan dari masalah yang berbeda. Di sini, adalah jumlah simpul dan adalah ukuran solusi. $1.2738^k + nk$ $2^n n^2$ $k=n$ $n$ $k$

Juga, pertanyaannya Apakah ada algoritma waktu subeksponensial untuk masalah NP-complete? menjawab pertanyaan serupa.

Pål GD
sumber

Pertanyaan menanyakan algoritma yang dikenal paling cepat dan tabel yang Anda tautkan memang memiliki algoritma "lebih cepat" daripada yang VC (khususnya yang subeksponensial), jadi mungkin bukan yang terbaik untuk dikutip.

Raphael

Lihat juga pertanyaan serupa ini dan jawaban David Eppstein Best-case Running-time untuk menyelesaikan masalah NP-Complete pada mathoverflow.

Pål GD

@Raphael Ya, misalnya Pengisian Minimum memiliki algoritma yang untuk setiap , berjalan dalam waktu .

ϵ > 0

$\epsilon > 0$

O ((1 + ϵ)^{k} + poly (n))

$O( (1+\epsilon)^k + \text{poly}(n))$

Pål GD