Kategori masalah NP-complete?

28

Apakah masuk akal untuk mempertimbangkan kategori dari semua masalah NP-lengkap, dengan morfisme sebagai pengurangan waktu-poli antara contoh yang berbeda? Adakah yang pernah menerbitkan makalah tentang ini, dan jika demikian, di mana saya dapat menemukannya?

cc.complexity-theory np-hardness ct.category-theory Paul Allen Grubbs
sumber
1
Saya tidak yakin mengapa Anda menginginkan kategori hanya masalah NP-complete, tetapi kategori semua masalah keputusan dengan beberapa gagasan tentang pengurangan (seperti pengurangan banyak-satu kali waktu polinomial) karena morfisme terdengar sebagai objek yang masuk akal untuk dipertimbangkan. Saya tidak tahu teori kategori sama sekali dan saya tidak bisa menebak apakah itu menarik atau tidak.
Tsuyoshi Ito
1
Tidak yakin ini membantu, tapi saya akan mencobanya: Pada isomorfisma dan kepadatan NP dan set lengkap lainnya . Lihat juga versi jurnal . Lihat juga kertas Mahaney .
MS Dousti
2
Hanya ingin menguraikan komentar Sadeq. Isomorfisme antara masalah lengkap telah dipelajari dan banyak pekerjaan telah dilakukan untuk membuktikan / menyangkal dugaan Berman-Hartmanis (yang menyatakan bahwa semua masalah lengkap adalah "isomorfik" di bawah waktu polinom banyak-satu pengurangan). Berikut ini adalah survei oleh Manindra Agrawal tentang dugaan isomorfisme ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). NPNP
Ramprasad
1
@ Tsuyoshi: bahkan kategori masalah NPC dengan pengurangan Karp berpotensi menarik - jika kita benar-benar memahami bahkan kategori itu, kita akan memiliki pemahaman yang lebih baik tentang kompleksitas secara umum (karena mungkin akan memerlukan pemahaman yang jauh lebih baik tentang Karp pengurangan, maka dari waktu polinomial). OTOH, saya tidak yakin bahwa melihatnya sebagai kategori akan memberikan jalan ke depan untuk membantu pemahaman. Saya telah memikirkan masalah ini beberapa di masa lalu, dan mencari referensi yang melihat kompleksitas dengan cara ini, dan tidak menemukan satupun. Saya harap seseorang melakukannya!
Joshua Grochow
3
Saya kedua Joshua. Yang penting adalah tidak mampu mendefinisikan suatu kategori, yang penting adalah menemukan struktur kategorikal yang menarik di dalamnya. Ada struktur yang menarik dalam kasus komputasi, tetapi untuk kompleksitas saya tidak tahu. Andrej harus tahu lebih baik dan semoga akan memeriksa pertanyaan ini.
Kaveh

Jawaban:

21

Area yang ingin Anda lihat disebut "teori kompleksitas implisit". Sejumlah nama acak untuk Google adalah Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, dan Kazushige Terui.

Teknik dasarnya adalah mengaitkan kelas kompleksitas dengan subsistem logika linier (yang disebut "logika linier cahaya"), dengan gagasan bahwa cut-elimination untuk sistem logis harus lengkap untuk kelas kompleksitas yang diberikan (seperti LOGSPACE, PTIME, dll). Kemudian melalui Curry-Howard Anda mengeluarkan bahasa pemrograman di mana tepatnya program-program di kelas yang diberikan dapat diekspresikan. Seperti yang mungkin Anda harapkan dari penyebutan logika linier, semua sistem ini kemudian memunculkan kategori tertutup monoid dari berbagai rasa, yang membuat Anda memiliki karakterisasi yang murni aljabar dan tidak tergantung mesin dari berbagai kelas kompleksitas.

Salah satu hal yang membuat daerah ini menarik adalah bahwa kompleksitas tradisional maupun metode logis / PL tidak sepenuhnya sesuai.

Karena kategori yang terlibat biasanya memiliki struktur tertutup, metode kombinatorik yang disukai oleh ahli teori kompleksitas sering rusak (karena program tingkat tinggi cenderung menolak karakterisasi kombinatorial). Contoh khas dari ini adalah kegagalan metode sintaksis untuk menangani kesetaraan kontekstual. Demikian pula, metode semantik juga mengalami masalah, karena mereka seringkali terlalu ekstensional (karena semantikis tradisional ingin menyembunyikan struktur fungsi internal). Contoh paling sederhana yang saya tahu di sini adalah penutupan LOGSPACE di bawah komposisi: ini adalah AFAIK hanya mungkin karena penghitungan ulang selektif dan selektif, dan Anda tidak dapat memperlakukan masalah sebagai kotak hitam murni.

Anda mungkin juga ingin memiliki keakraban dengan semantik permainan dan Geometry of Interaksi Interaksi Girard (dan pendahulu mereka, struktur data konkret Kahn-Plotkin-Berry) jika Anda serius dalam bidang ini - ide-ide representasi token-passing dari yang lebih tinggi- perhitungan pesanan yang digunakan dalam pekerjaan ini memasok banyak intuisi untuk ICC.

Karena saya telah menunjukkan peran sentral kategori monoid dalam karya ini, Anda mungkin bertanya-tanya tentang koneksi ke GCT Mulmuley. Sayangnya, saya tidak dapat membantu Anda di sini, karena saya tidak cukup tahu. Paul-André Melliès mungkin orang yang baik untuk ditanyakan.

Neel Krishnaswami
sumber
16

Mungkin untuk mengkategorikan banyak hal, tetapi itu tidak selalu berarti mereka termasuk kategori yang menarik. Jadi jawaban untuk "apakah itu masuk akal" tergantung pada maksud Anda.

Adapun untuk memprediksi apakah itu akan menarik, asumsikan beberapa definisi pengurangan yang tepat sehingga membentuk kategori, NPC. Kategori pertanyaan yang menarik secara teoretis adalah hal-hal seperti menanyakan apakah NPC memiliki berbagai batasan atau kolim (misalnya, produk, produk, penarikan, pushout, ...). Jadi sebelum membahas pekerjaan memformalkan sesuatu, akan baik untuk duduk dan berpikir tentang apa arti batasan ini dan apakah makna itu akan menarik untuk diketahui. Jika kita menganggap NPC memiliki mundurnya, maka apakah kemampuan untuk mengambil mundurnya dua pengurangan berarti sesuatu yang istimewa? Pertanyaan-pertanyaan seperti ini sepertinya menarik jika kita ingin mencari tahu apa masalah NP-selesai "atomik", atau bagaimana beberapa masalah NP-lengkap (atau pengurangannya) dapat digabungkan;

Beberapa mengikuti pertanyaan akan hal-hal seperti: apakah NPC memiliki subkategori menarik? Apakah NPC adalah subkategori dari kategori menarik yang lebih besar? Kita sudah tahu banyak tentang bagaimana masalah NP-lengkap berhubungan dengan kelas masalah lainnya, jadi jawaban dugaan untuk pertanyaan-pertanyaan ini adalah "tentu saja". Tetapi untuk menempatkan poin yang lebih baik di atasnya, apa yang mempertimbangkan hubungan-hubungan ini dari perspektif teori kategori menawarkan bahwa perspektif lain tidak? Satu hal yang dapat ditawarkan CT adalah pertanyaan apakah ada tambahan non-sepele antara NPC dan kategori lainnya. Tentu saja, tambahan terutama menarik ketika kategori di belakangnya sendiri menarik, jadi jika NPC tidak memiliki banyak struktur khusus maka mengetahui tentang tambahan-NPC tidak akan banyak menawarkan.

Adapun referensi tertentu, saya tidak tahu apa-apa tapi tautan dalam komentar oleh Sadeq, Ramprasad, Kaveh harus menyediakan tempat untuk memulai.

wren romano
sumber