Batas Bawah pada Waktu Berjalan Algoritma Grafik

8

Apakah ada batas bawah non-sepele pada waktu berjalan algoritma grafik dalam RAM / PRAM / model perhitungan? Saya tidak mencari hasil NP-Hardness di sini.

Berikut ini adalah hasil yang bisa saya temukan [lihat ref L92]:

  • 3-Pewarnaan dari n-cycle membutuhkan waktu .Ω(catatan∗⁡n)

Saya ingin tahu apakah ada kemajuan / kerja untuk mendapatkan batas yang lebih rendah untuk masalah seperti: Jalur Terpendek (dengan / tanpa bobot negatif), Mincut, st Arus maksimum, pencocokan maksimum (kardinalitas / bobot). Referensi apa pun yang terkait dengan ini sangat dihargai dan membantu.

Referensi

[ L92 ] N. Linial, Lokalitas dalam algoritma grafik terdistribusi, SIAM Journal on Cominging, 1992, 21 (1), hlm. 193-201

EDIT: Seperti yang disarankan oleh Robin Kothari dalam komentar, saya membuat pertanyaan lebih terarah.

cc.complexity-theory reference-request graph-algorithms lower-bounds rizwanhudda
sumber
5
Tanpa membatasi model, jawaban yang memadai untuk pertanyaan ini bisa berlanjut ke halaman. Selain pembatasan masalah grafik, pertanyaan ini pada dasarnya menanyakan "Batas bawah apa yang diketahui dalam CS?" Dan pembatasan untuk masalah grafik tidak kuat, karena dalam model di mana kami dapat membuktikan batas bawah yang baik untuk beberapa masalah (misalnya, streaming, pohon keputusan, kompleksitas komunikasi), kami dapat membuktikan batas bawah yang baik untuk masalah grafik juga.
Robin Kothari
@RobinKothari Saya telah mengedit pertanyaannya sekarang saya mencari batas bawah dalam model PRAM / RAM. Apakah Anda menyarankan perubahan lagi?
rizwanhudda

Jawaban:

3

Dalam model PRAM tanpa operasi bit , batas bawah yang cukup kuat diketahui. Misalnya, dalam model ini, seseorang tidak dapat menyelesaikan min-cut dalam waktu pada prosesor [1].2 O ( √HAI(n)2HAI(n)

Meskipun merupakan model terbatas, ia cukup kuat untuk menghitung determinan secara efisien, dan mencakup sebagian besar algoritma standar untuk masalah optimisasi kombinatorial poli waktu. Lihat di sini , di sini , atau kertas asli untuk lebih jelasnya.

[1] Mulmuley, K. Batas Bawah dalam Model Paralel tanpa Operasi Bit . SIAM J. Comput., 28 (4), 1460–1509, 1999. ( dari halaman web penulis tanpa paywall )

Joshua Grochow
sumber