Masalah alam paling sulit diketahui dalam P?

33

Saya bertanya-tanya, apa yang (saat ini) merupakan angka terbesar , sehingga masalah alami diketahui dengan sifat-sifat berikut:k

  1. Sebuah algoritma telah sudah ditemukan masalah.O(nk)

  2. Untuk setiap algoritma no O ( n k - ϵ ) yang diperbaiki dikenal untuk masalah yang sama. (Perhatikan bahwa algoritma yang lebih cepat ada, hanya saja belum diketahui, jadi saya tidak mencari batas bawah yang terbukti.)ϵ>0O(nkϵ)may

  3. Deskripsi masalah itu sendiri tidak bergantung pada . (Kondisi ini diperlukan untuk mengecualikan kasus parametrized seperti "temukan klik ukuran dalam grafik input, untuk konstanta .")kkk

Dalam arti tertentu, masalah seperti itu mungkin memenuhi syarat sebagai masalah yang paling sulit, diketahui, alami, dalam (mengenai eksponen dari algoritma yang paling cepat diketahui).P

Andras Farago
sumber
9
Coba ini mungkin? cstheory.stackexchange.com/q/6660/1800
Hsien-Chih Chang 張顯 之
Terima kasih, saya tidak mengetahui pos itu. Ada banyak jawaban menarik.
Andras Farago
11
Pos terkait lainnya adalah cs.stackexchange.com/questions/13202/…
vb le
eksponen matriks perkalian bisa cocok sebagai jawaban?
T ....

Jawaban:

16

O(|V|8)

O(|V|12|E|)P5

BPR
sumber