Apakah ada yang diketahui kelas kompleksitas yang mengandung mitra online masalah optimasi?

10

Apakah ada yang diketahui kelas kompleksitas yang mengandung mitra online masalah optimasi? Jika tidak, lalu bagaimana kelas tersebut dapat didefinisikan?

Kita tahu bahwa banyak masalah memiliki versi online mereka: misalnya versi online dari masalah pengemasan bin. Masalah online lebih sulit diukur dengan rasio kompetitif mereka.

Dan saya belum menemukan yang serupa di kebun binatang kompleksitas .

Pada dasarnya, kita dapat mengatakan bahwa tidak ada masalah online, tetapi hanya algoritma online untuk masalah offline. Namun, jika ada masalah online, mengapa tidak ada kelas kompleksitas yang mengandungnya?

cc.complexity-theory complexity-classes Oleksandr Bondarenko
sumber
Apakah ini terkait dengan algoritma stream ( cstheory.stackexchange.com/search?q=stream )?
MS Dousti
1
Algoritme online tidak sama dengan algoritma aliran: dalam streaming, faktor pembatasnya adalah ruang mesin streaming (sehingga hanya memiliki memori jangka pendek). Dalam algoritma online, faktor pembatasnya adalah kurangnya pengetahuan tentang apa yang akan terjadi (sehingga memiliki miopia ekstrem)
Suresh Venkat
@ Suresh: Oh, begitu. Terimakasih atas klarifikasinya.
MS Dousti

Jawaban:

4

Salah satu aspek rumit dari mendefinisikan kelas kompleksitas untuk masalah online adalah bahwa pada prinsipnya tidak ada batasan pada jenis komputasi apa yang dapat saya lakukan setelah saya membaca input. Dengan kata lain, masalah online sulit walaupun saya memiliki (misalnya) oracle NP yang memproses input begitu input diterima.

Bisa dibayangkan bahwa dengan prosesor yang lebih terbatas, tugas prediksi yang lebih sederhana menjadi lebih sulit untuk dilakukan, tetapi secara umum kesulitan merancang algoritma online berasal dari kemampuan musuh untuk mengubah input setelah Anda membuat model prediksi.

Suresh Venkat
sumber
Bagaimana tidak ada batasan pada jenis perhitungan yang mempengaruhi kekerasan masalah daring: bisakah Anda menjelaskannya?
Oleksandr Bondarenko
yah, kelas kompleksitas tipikal Anda biasanya didefinisikan dalam beberapa jenis sumber daya terikat. Maksud saya adalah bahwa masalah online (seperti -server) sulit dengan cara yang tidak bergantung pada model kompleksitas untuk mesin yang mendasarinya. K
Suresh Venkat
Karena sumber daya terbatas (selain waktu dan ruang klasik) untuk algoritma online adalah informasi tentang contoh lengkap masalah yang diberikan, jika kita dapat mendefinisikan gagasan informasi untuk tujuan ini dengan cara yang ketat, maka dapatkah kita berbicara tentang kompleksitas kelas untuk masalah online?
Oleksandr Bondarenko
1
Anda bisa. Saya tidak tahu apakah ini sudah dilakukan. Saya berasumsi Anda telah memeriksa buku Borodin / El-Yaniv?
Suresh Venkat
1
Saya telah membaca buku Borodin / El-Yaniv tetapi belum menemukan formalisasi gagasan informasi. Namun, ada makalah yang menarik tentang kompleksitas saran ( scholar.google.com/... ).
Oleksandr Bondarenko
0

Baru-baru ini saya membaca makalah "Game melawan alam" (Papadimitriou, 1985) (di sini adalah tautannya: http://www.sciencedirect.com/science/article/pii/0022000085900455 ). Secara khusus, makalah ini membuktikan bahwa Kepuasan Stochastic (SSAT) adalah PSPACE-complete. Saya kira SSAT adalah masalah online? Jadi makalah ini agak terkait dengan pertanyaan Anda?

Saya juga cukup tertarik dengan masalah kompleksitas untuk masalah online. Kita bisa berdiskusi!

Pria bodoh
sumber