Dapatkah masalah NP-hard menjadi polinomial rata-rata?

11

Saya bertanya-tanya apakah ada masalah -hard yang rata-rata "polinomial" dalam kasus rata-rata. Saya pikir ada dua cara untuk menafsirkan ini?NP

  • Jika , bisa ada sebuah algoritma pemecahan suatu N P masalah -Hard dengan diamortisasi (rata-rata kasus) waktu berjalan dari O ( n k ) untuk konstan k ?P≠NPNPO(nk)k
  • Apakah ada masalah yang yang juga di B P P , atau bahkan P P ?NPBPPPP

Adakah yang bisa menjawab atau memberikan referensi untuk menjawab salah satu dari pertanyaan ini?

complexity-theory reference-request np-complete probabilistic-algorithms amortized-analysis Ya ampun
sumber
5
Pertanyaan ini muncul dalam teori CS beberapa waktu lalu, di sini adalah tautan cstheory.stackexchange.com/questions/496/…
lPlant
Ah, bagus sekali! Haruskah saya menutup / menghapus pertanyaan ini?
jmite
2
@jmite: Ini mungkin berguna untuk tetap di sini, jadi mungkin mengirim jawaban cepat (mandiri) dengan referensi di sini?
Raphael
1
Saya hanya ingin menunjukkan bahwa amortisasi tidak sama dengan waktu rata-rata berjalan.
Gardenhead
PH⊆PPP

Jawaban:

5

Tampaknya pertanyaan telah dijawab di CSTheory.SE .

Ringkasan: memang, memang mungkin.

O(n)

NP

Ya ampun
sumber