Masalah dengan Agoritma Waktu Eksponensial Tunggal Tidak Diketahui

8

Saya mencari contoh masalah yang mudah untuk mendapatkan algoritma yang berjalan dalam waktu , atau 2 O ( n c ) untuk beberapa c > 1 tetapi yang tidak diketahui apakah ada algoritma berjalan dalam waktu 2 O ( n ) .2O(nlogn)2O(nc)c>12O(n)

Saya sebagian besar tertarik pada masalah teori grafik, tetapi contoh-contoh bagus lainnya juga akan diterima.

Sebagai contoh, adalah sepele untuk mengembangkan suatu algoritma yang berjalan pada waktu untuk masalah jalur Hamiltonian. Cukup uji semua permutasi. Namun, menggunakan pemrograman dinamis, seseorang dapat mencapai waktu 2 O ( n ) . Apakah ada masalah konektivitas alami lainnya, atau variasi masalah jalur Hamiltonian yang tidak diketahui algoritme yang berjalan dalam waktu 2 O ( n ) ?O(n!)=2O(nlogn)2O(n)2O(n)

memverifikasi
sumber

Jawaban:

8

GHhGHuvE(G)h(u)h(v)E(H)

O(|V(H)||V(G))O

O(c|V(H)|+|V(G)|)

Serge Gaspers
sumber
5
O(c|V(H)|+|V(G)|)
Terima kasih untuk penunjuknya! Bagian terakhir dari makalah itu juga mengandung lebih banyak masalah penyisipan konkret yang tidak jelas apakah algoritma waktu eksponensial tunggal dapat diperoleh.
Serge Gaspers
7

Isomorfisme Permutasi Kelompok Permutasi, alias Konjugasi Grup Permutasi:

Sn(π1,,πk)(ρ1,,ρ)

πSnπ1π1,,πkπ=ρ1,,ρ

π1,,πkπi

n!=2O(nlogn)2O(n)|G|O(1)G=π1,,πk|G|n!G=Snn!/nO(1)G|G|

G2O(n)|G|O(1)

Joshua Grochow
sumber
6

O(nlogn)

David Eppstein
sumber