Apakah itu aturan bahwa masalah diskrit adalah NP-keras dan masalah terus menerus tidak?

27

Dalam pendidikan ilmu komputer saya, saya semakin memperhatikan bahwa sebagian besar masalah diskrit adalah NP-lengkap (setidaknya), sedangkan mengoptimalkan masalah terus menerus hampir selalu mudah dicapai, biasanya melalui teknik gradien. Apakah ada pengecualian untuk ini?

cc.complexity-theory co.combinatorics optimization alekdimi
sumber

14

Pasti ada, banyak dari mereka. Pencocokan bipartit dan umum, dan pemotongan minimum adalah tiga masalah diskrit klasik waktu polinomial yang dapat dipecahkan. Banyak masalah optimisasi non-cembung terus-menerus adalah NP-hard: menemukan diameter set cembung, atau menghitung norma injeksi dari tensor 3-d.

Sasho Nikolov

6

Berikut adalah masalah pengoptimalan berkelanjutan sederhana yang sulit dipecahkan NP

Jukka Suomela

8

Saya tidak yakin masalah apa yang ada dalam pikiran Anda, tetapi banyak masalah berkelanjutan yang "diselesaikan" dengan metode gradien tidak benar-benar "terpecahkan": metode ini hanya menemukan beberapa jenis lokal optimal.

Suresh Venkat

1

Semua tanggapan sejauh ini tampaknya merupakan contoh tandingan, tetapi akan menyenangkan untuk melihat beberapa kasus di mana aturan ini tampaknya berlaku. Dua yang muncul dalam pikiran adalah pemrograman linier vs pemrograman integer dan optimasi cembung vs maksimalisasi submodular.

usul

13

Saya pikir seluruh diskrit vs terus menerus adalah ikan haring merah. Suatu masalah harus memiliki struktur yang sangat khusus untuk dapat dipecahkan secara efisien. Saya pikir perbedaan nyata di sini adalah bahwa dalam kasus masalah kontinu mudah struktur khusus cenderung cembung, sedangkan dalam kasus masalah diskrit mudah hal-hal terlihat lebih rumit: kadang-kadang struktur submodularity atau persimpangan matroid, tetapi seringkali tidak. Ini mungkin lebih berkaitan dengan fakta bahwa kita belum memahami matematika diskrit dengan sangat baik.

Sasho Nikolov

41

Contoh yang saya sukai adalah masalah di mana, diberi , tentukan apakah: $a_1, a_2, \ldots, a_n \in \mathbb{N}$

\int_{- π}^{π} \cos (a_{1} z) \cos (a_{2} z) \dots \cos (a_{n} z) d z \neq 0

$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$

Ini awalnya tampak seperti masalah terus menerus untuk mengevaluasi integral ini, namun mudah untuk menunjukkan bahwa integral ini bukan nol jika ada partisi seimbang dari set , jadi masalah integral ini adalah sebenarnya NP-lengkap. $\{a_1, \ldots, a_n\}$

Tentu saja, saya mendorong bermain-main dengan beberapa alat numerik untuk meyakinkan diri sendiri bahwa sebagian besar (jika tidak semua) trik numerik untuk mengevaluasi integral ini ditakdirkan untuk gagal begitu menjadi cukup besar. $n$

Joe Bebel
sumber

4

Karena kita sedang membahas topik ini, referensi paling awal untuk masalah ini yang dapat saya temukan adalah dalam "The Nature of Computation" oleh Moore and Mertens. Mereka tidak memberikan referensi, jadi saya berasumsi mereka menciptakannya, atau itu berasal dari cerita rakyat. Saya akan sangat menghargai jika seseorang tahu sumber masalah ini.

Joe Bebel

Mungkin bukan hanya sebagian besar tetapi semua teknik numerik akan skala serempak untuk cukup besar ? Karena masalahnya NP-complete, teknik numerik yang akurat untuk mengevaluasi integral yang diskalakan secara polinomi dalam akan cukup untuk menunjukkan P = NP.

n

$n$

n

$n$

EP

1

Benar, sebuah algoritma yang selalu mengevaluasi integral dengan benar dalam polinomial waktu dalam akan cukup untuk menunjukkan P = NP. Di sisi lain, saya tidak bisa 100% mengesampingkan kemungkinan teknik numerik tertentu yang saya tidak sadari entah bagaimana melakukannya dengan baik pada contoh spesifik integral ini, bahkan ketika besar, seperti bagaimana pemecah SAT sering mampu untuk menemukan tugas yang memuaskan untuk beberapa rumus dengan ribuan variabel, meskipun kinerja kasus terburuk buruk. Jadi, bahkan jika saya ragu metode seperti itu ada, saya lindung nilai jawaban saya sedikit.

n

$n$

n

$n$

Joe Bebel

3

Rupanya sumber asli dari masalah ini adalah: David Plaisted, Beberapa masalah pembagian polinomial dan bilangan bulat NP-hard. SIAM Journal on Computing, 7 (4): 458-464, 1978. Rujukannya ada di belakang Moore dan Mertens, hanya saja tidak ada di badan teks itu sendiri.

Joe Bebel

26

Ada banyak masalah terus-menerus dari bentuk "tes apakah input kombinatorial ini dapat direalisasikan sebagai struktur geometris" yang lengkap untuk teori eksistensial real , analog kontinu dari NP. Secara khusus, ini menyiratkan bahwa masalah-masalah ini NP-keras daripada dipecahkan secara polinomi. Contohnya termasuk menguji apakah grafik yang diberikan adalah grafik jarak unit, apakah grafik yang diberikan dapat ditarik di pesawat dengan tepi segmen garis lurus dan paling banyak jumlah penyeberangan tertentu, atau apakah pengaturan pseudolin yang diberikan dapat ditarik untuk membentuk garis pengaturan.

Ada masalah terus menerus lainnya yang bahkan lebih sulit: misalnya, menemukan jalur terpendek di antara hambatan polyhedral di 3d adalah PSPACE-complete (Canny & Reif, FOCS'87).

David Eppstein
sumber

1

'Jalur terpendek di antara rintangan polihedral' hanya berkelanjutan dalam nama saja, bukan? Kita dapat menganggap ruang konfigurasi sebagai penyatuan sejumlah potongan diskrit yang sesuai dengan jalur yang 'memeluk' serangkaian rintangan tertentu; maka optimasi lokal dalam setiap bagian yang diberikan (yaitu, dalam set hambatan yang diberikan) sangat mudah tetapi menentukan jalur mana yang memiliki jarak terbaik secara global adalah bagian sulit dari masalah tersebut.

Steven Stadnicki

13

Meskipun ini tidak persis menjawab pertanyaan awal Anda, ini adalah contoh (dugaan) dari semacam tandingan filosofis: masalah di mana presentasi itu terpisah tetapi semua kekerasan berasal dari aspek 'berkelanjutan' dari masalah.

Masalahnya adalah masalah Jumlah Akar Kuadrat : diberikan dua set bilangan bulat dan , adalah ? (Ada formulasi lain, tapi ini adalah yang saya inginkan.) Meskipun tidak diketahui secara pasti untuk menjadi $A=\{a_1, a_2, \ldots, a_m\}$ $B=\{b_1, b_2, \ldots, b_n\}$ $\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$ keras, secara luas diduga bahwa ini mungkin NP-hard dan mungkin sebenarnya berada di luar NP (ada, seperti yang disebutkan dalam komentar, alasan yang sangat baik untuk percaya bahwa itu bukan NP-lengkap); satu-satunya penahanan yang diketahui hingga saat ini adalah beberapa tingkat lebih tinggi di atas hierarki polinomial. Jelas penyajian masalah ini sama jelasnya seperti - seperangkat bilangan bulat dan pertanyaan ya / tidak tentang mereka - tetapi tantangan muncul karena meskipun menghitung akar kuadrat dengan presisi tertentu adalah masalah yang mudah, mereka mungkin perlu dihitung ke akurasi tinggi (berpotensi superpolinomial) untuk menyelesaikan ketidaksetaraan dengan satu atau lain cara. Ini adalah masalah 'diskrit' yang muncul dalam sejumlah konteks optimasi yang mengejutkan dan membantu berkontribusi pada kompleksitasnya sendiri.

Steven Stadnicki
sumber

4

Saya juga suka contoh ini, meskipun perlu ditunjukkan bahwa ada alasan kuat untuk meyakini bahwa ini bukan NP-complete; lihat ( cstheory.stackexchange.com/a/4010/8985 )

Joe Bebel

@ JoBebel Poin yang sangat bagus - Saya telah sedikit merevisi bahasa saya untuk mencerminkan hal itu. Terima kasih!

Steven Stadnicki

6

Masalah diskrit biasanya cenderung lebih sulit (mis. LP vs. ILP) tetapi bukan diskretitas itu sendiri yang menjadi masalahnya ... melainkan bagaimana kendala memengaruhi cara Anda dapat mencari domain Anda. Sebagai contoh, Anda mungkin berpikir bahwa mengoptimalkan polinomial adalah sesuatu yang dapat Anda lakukan secara efisien, tetapi memutuskan konveksitas kuartik (derajat-4 polinomial) adalah NP-hard .

Yang berarti bahkan jika Anda sudah memiliki yang optimal, cukup membuktikan bahwa Anda berada di optimal sudah NP-keras.

Mehrdad
sumber

Saya pikir diskresi juga merupakan bagian dari masalah. Katakan misalnya Anda akan memiliki jaminan ILP LP. Misalnya Anda bisa mencari solusi untuk varian LP, tetapi masih ada 2^n" tetangga menarik " yang perlu Anda cari.

Willem Van Onsem

@ ComuSoft: Tidak juga ... perbedaan bukanlah masalahnya. Lihat masalah jalur terpendek , yang merupakan masalah diskrit tetapi tetap mereduksi menjadi kasus khusus pemrograman linier integral , yang dapat dipecahkan dengan P-time (jangan dikacaukan dengan pemrograman linear integer , yang jelas NP-hard).

Mehrdad

itu tidak terlalu mengejutkan: karena pemrograman linear integer adalah NP-lengkap, setiap masalah dalam P (yang dapat diselesaikan dalam waktu poli), dapat ditransformasikan dalam waktu poli dalam masalah ILP.

Willem Van Onsem

@ Comommoft: Apakah Anda membaca komentar sepenuhnya? Saya tidak berbicara tentang ILP.

Mehrdad

maaf, baca cepat. Tapi tetap saja itu karena kendala-kendalanya adalah total unimodular , jadi hanya dengan "rahmat" kendala-kendala yang terstruktur dengan baik, masalah-masalah seperti itu mudah dipecahkan. Secara umum diskritisasi merupakan aspek yang bermasalah dalam masalah.

Willem Van Onsem

5

Meskipun untuk beberapa masalah populer, memang benar, saya pikir kedua asumsi - tergantung pada apa yang Anda definisikan sebagai masalah optimasi - tidak benar.

Pertama, beberapa definisi: kebanyakan masalah optimisasi bukan bagian dari NP . Misalnya untuk masalah Knapsack : seseorang tidak dapat mengeksploitasi non-determinisme untuk membangun tas yang paling berharga, sederhana karena cabang-cabang non-deterministik yang berbeda tidak memiliki memori bersama. NP juga didefinisikan sebagai "dapat diverifikasi secara polinomi" (memverifikasi sertifikat) [1, p. 34]. Dalam hal ini sertifikat misalnya tas : bitstring di mana jika bit ke- i diatur, itu menyiratkan item ke- i adalah bagian dari tas. Anda memang dapat memeriksa dalam waktu polinomial jika tas seperti itu lebih berharga daripada ambang yang diberikan (ini adalah varian keputusan), tetapi Anda tidak dapat - sejauh yang kami ketahui - berdasarkan pada satu tas, (jumlah polinomial tas), memutuskan apakah tas tersebut adalah yang paling berharga dari semua tas yang mungkin. Itu perbedaan penting antara NP dan EXP misalnya : di EXP , Anda dapat menghitung semua tas yang mungkin dan melakukan pembukuan tentang tas mana yang terbaik.

The varian keputusan dari masalah optimasi dalam beberapa kasus bagian dari NP , salah satu kebutuhan untuk membuat perbedaan yang jelas antara rasa maksimalisasi dan rasa keputusan . Dalam pilihan rasa, pertanyaannya adalah: " Mengingat masalah optimisasi, dan batas utilitas, apakah ada solusi dengan utilitas lebih besar atau sama dengan batas itu " (atau sedikit dimodifikasi untuk masalah minimisasi).

Saya juga menganggap bahwa dengan NP Anda berarti (hipotetis) bagian dari NP yang bukan merupakan bagian dari P . Jika P = NP , tentu saja NP-complete masih ada, tetapi itu akan sama dengan P (hanya bertepatan dengan P untuk beberapa pengertian reduksi, seperti pengurangan banyak-waktu polinomial-kali oleh @ AndrásSalamon), yang tidak terlalu mengesankan ( dan akan mengurangi " celah " yang Anda sebutkan dalam pertanyaan Anda).

Saya semakin memperhatikan bahwa sebagian besar masalah diskrit adalah NP-lengkap.

Sekarang kami telah menyortirnya: ada banyak masalah optimasi yang ada di P : masalah jalur terpendek , masalah aliran maksimum (untuk kapasitas integral), pohon rentang minimum dan pencocokan maksimum . Meskipun masalah ini mungkin terlihat "sepele untuk dipecahkan" bagi Anda, ini masih merupakan masalah pengoptimalan, dan dalam banyak kasus konstruksi (dan membuktikan kebenaran) tidak semudah itu. Jadi klaim tidak memiliki semua masalah diskrit lengkap NP. Mengingat P tidak sama dengan NP , masalah-masalah ini karenanya tidak bisa NP-lengkap .

$\Sigma^P_i$

Sedangkan mengoptimalkan masalah yang berkelanjutan hampir selalu mudah dicapai.

Masalah berkelanjutan populer yang NP-hard adalah pemrograman kuadratik .

$\vec{x}$

\frac{{\vec{x}}^{T} \cdot Q \cdot \vec{x}}{2} + {\vec{c}}^{T} \cdot \vec{x}

$\dfrac{\vec{x}^T\cdot Q\cdot\vec{x}}{2}+\vec{c}^T\cdot\vec{x}$

A \cdot \vec{x} \leq \vec{b}

$A\cdot\vec{x}\leq\vec{b}$

Sebenarnya pemrograman Linear telah lama dianggap NP-keras juga, tetapi dengan heuristik yang berkinerja sangat baik ( metode Simplex ). Algoritma Karmarkar ini adalah namun di P .

Dari saat masalah optimasi berkaitan dengan objek non-cembung, secara umum akan sulit - jika bukan tidak mungkin - untuk menemukan algoritma yang efisien.

Bibliografi

[1] Kompleksitas Komputasi, pendekatan modern , Sanjeev Arora dan Boaz Barak

Willem Van Onsem
sumber

2

Paragraf definisi memang agak membingungkan. Knapsack adalah masalah optimisasi NP. Tidak benar bahwa "tidak diketahui" jika versi optimisasi dalam NP: tidak, hanya dengan definisi. Juga saya tidak berpikir kita tahu ada masalah yang bersyarat NP-lengkap pada NP tidak sama dengan PI 3-SAT akan NP-lengkap bahkan jika P = NP (sebenarnya jika P = NP setiap masalah dalam P adalah NP selesai).

Sasho Nikolov

@ AndrásSalamon: titik diambil. Saya menghapus bagian itu. Memang agak ceroboh.

Willem Van Onsem

@ AndrásSalamon: ternyata itu benar. Oleh karena itu dikatakan: " Mengingat P tidak sama dengan NP, masalah-masalah ini karenanya tidak dapat NP-lengkap. "

Willem Van Onsem

@ AndrásSalamon: Nah jika P=NP, setiap masalah dalam NP-complete adalah dengan definisi bagian dari NP dan dengan demikian dengan memperpanjang P , sekarang P berarti ada algoritma polinomial. Intinya adalah, saya pikir transformasi tidak masalah, karena untuk setiap bahasa di P pasti ada algoritma polinomial. Apakah Anda mengambil (paling banyak polinomial) transformasi atau tidak, tidak relevan. Ini masih polinomial, dengan demikian dalam P . Dengan kata lain, karena elemen asli dalam P , Anda dapat mengambil setiap transformasi poly-time secara gratis (tidak menghasilkan kelas kompleksitas yang lebih tinggi).

Willem Van Onsem

2

Knapsack sebagai masalah optimisasi tentu bukan NP-complete, karena ini bukan masalah keputusan, jadi bukan di NP. Bagaimanapun, saya mengerti apa yang Anda katakan, tapi ini adalah jenis rincian tingkat sarjana yang menurut saya harus diterima begitu saja di forum tingkat penelitian seperti CStheory @ SE, sama seperti saya tidak berharap untuk melihat penjelasan tentang bagaimana konvergensi dalam probabilitas tidak sama dengan konvergensi yang hampir pasti pada Mathoverflow.

Sasho Nikolov

Apakah itu aturan bahwa masalah diskrit adalah NP-keras dan masalah terus menerus tidak?

Jawaban: