Masalah untuk dikurangi dari untuk membuktikan

Apa masalah standar yang dapat kita kurangi untuk membuktikan batas bawah? $\Omega(n\log n)$

Tentu saja, nyatakan masalah selain penyortiran dan perbedaan elemen.

cc.complexity-theory lower-bounds Vinayak Pathak
sumber

Dalam model komputasi apa?

KIA

Poin yang bagus. Maksud saya model berbasis perbandingan.

Vinayak Pathak

Jawaban:

$\Omega(n\log n)$

$n$
$n$
$n$
$n$
Tetapkan penyertaan: Diberikan dua set bilangan real, apakah satu merupakan subset dari yang lain?
$[n]$

Tiga yang pertama adalah yang paling sering digunakan dalam geometri komputasi.

Jeffε
sumber

selain tidak relevan: tiga yang pertama juga merupakan masalah keras kanonik untuk algoritma streaming berbasis kompleksitas komunikasi batas bawah.

Suresh Venkat

@ SureshVenkat - Saya telah melihat set disjointness dan set kesetaraan yang digunakan untuk membuktikan batas bawah dalam streaming. Apakah Anda memiliki contoh perbedaan elemen?

Vinayak Pathak

Setidaknya satu tempat yang saya lihat dalam analisis algoritma di bawah model W-stream. Secara umum, ED terkait erat dengan disjointness bit-vector (atau set)

Suresh Venkat