Masalah optimasi paling sulit di NC

8

Saat mempelajari masalah optimisasi, kami biasanya menganggap pemrograman linier (atau lebih umum: optimisasi cembung) sebagai contoh paling sederhana. Ini dapat dipecahkan dalam waktu polinomial, dan memiliki algoritma yang relatif mudah dipahami. Namun, versi keputusan LP adalah -lengkap. Ini menunjukkan bahwa ini adalah salah satu masalah tersulit yang dapat kita pecahkan dalam waktu polinomial. $\mathsf{P}$

Dengan asumsi bahwa . Apa jenis alami masalah optimasi yang paling sulit dengan masalah keputusan di ? $\mathsf{NC} \neq \mathsf{P}$ $\mathsf{NC}$

Jika ini terlalu kabur, maka kita dapat membatasi batasan. Apa batasan minimal yang perlu kita tempatkan pada program linear (atau lebih umum: program cembung) untuk memungkinkan masalah keputusan yang terkait dengan program terbatas dapat dipecahkan dalam ? $\mathsf{NC}$

Motivasi

Sebagian besar, ini adalah keingintahuan kosong. Namun, itu disebabkan oleh Cosma Shalizi " Di Uni Soviet, Masalah Optimasi Memecahkan Anda ". Secara khusus, jika LP terlalu sulit untuk diselesaikan untuk memiliki ekonomi yang tersentralisasi (yaitu mengoptimalkan dalam meminta terlalu banyak), maka setiap sistem yang didesentralisasi harus melakukan semacam pemrosesan paralel lebih cepat daripada waktu-poli (bagi saya : ). $\mathsf{P}$ $\mathsf{NC}$

cc.complexity-theory optimization linear-programming Artem Kaznatcheev
sumber

Karena NC adalah hierarki, Anda tidak mungkin menemukan masalah "paling sulit" di NC (lebih tepatnya: NC tidak memiliki masalah lengkap kecuali hierarki NC runtuh). Demikian pula, mungkin tidak ada batasan minimal "universal" pada LP untuk memasukkannya ke dalam NC, meskipun ini tampaknya lebih sulit untuk dikesampingkan, bahkan dikondisikan pada asumsi alami. (Ini bukan untuk mengurangi pertanyaan - Saya suka pertanyaan, dan itu jelas menghasilkan beberapa jawaban yang menarik - hanya sebuah komentar.)

Joshua Grochow

9

Apakah Anda mengetahui pekerjaan pada piringan hitam / SDP positif? Ada banyak hasil di daerah tersebut, sebagian besar di sepanjang garis "jika kendala LP / SDP positif, maka masalahnya dapat diselesaikan di NC."

Beberapa referensi penting dalam pekerjaan ini adalah Luby-Nisan 93 dan Jain-Yao 11 . Sumber lain yang luar biasa adalah slide pembicaraan Rahul Jain ini pada konferensi "Kemajuan Terbaru dalam Algoritma Quantum" di IQC. Seluruh pembicaraan tersedia di youtube.

Robin Kothari
sumber

1

P O

$\mathsf{PO}$

N C

$\mathsf{NC}$

N C

$\mathsf{NC}$

N C O

$\mathsf{NCO}$

P = N C

$\mathsf{P} = \mathsf{NC}$

P

$P$

2

Saya tidak yakin, tetapi Anda mungkin tertarik - jika tidak, saya mohon maaf - pada makalah berikut , yang tidak terkait dengan jenis alami masalah pengoptimalan, tetapi berurusan dengan masalah yang dapat direduksi menjadi masalah pengoptimalan tertentu , yang solusinya ada di NC.

Igor Averbakh, Oded Berman, "Paralel-algoritma NC untuk masalah lokasi multifasilitas dengan komunikasi timbal balik dan aplikasi mereka", Networks, Volume 40, Edisi 1, halaman 1-12, Agustus 2002, Wiley

DOI: 10.1002 / net.10027

Abstrak

Masalah umum yang dipelajari adalah untuk menemukan p fasilitas yang dapat dibedakan pada pohon untuk memenuhi batasan batas atas pada jarak antara pasangan fasilitas, mengingat bahwa setiap fasilitas harus ditempatkan di dalam wilayah yang layak, yang didefinisikan sebagai subtree pohon. Kami menyajikan skema lokasi paralel (PLS) untuk menyelesaikan masalah yang dapat diimplementasikan sebagai algoritma-NC. Kami juga memperkenalkan algoritme NC paralel berdasarkan PLS untuk versi minimum masalah, termasuk masalah p-center kendala jarak dengan komunikasi timbal balik. Menggabungkan PLS dan teknik parametrik Megido yang ditingkatkan, kami mengembangkan algoritma serial polinomial yang kuat untuk masalah minimax; algoritma memiliki kompleksitas terbaik yang saat ini tersedia dalam literatur.

Massimo Cafaro
sumber

Masalah optimasi paling sulit di NC

Motivasi

Jawaban: