Masalah Antara P dan NPC

Anjak dan grafik isomorfisme adalah masalah dalam NP yang tidak diketahui dalam P atau NP-Complete. Apa saja masalah alam lain (yang cukup berbeda) yang berbagi properti ini? Contoh buatan yang datang langsung dari bukti teorema Ladner tidak masuk hitungan.

Apakah ada di antara contoh ini yang terbukti sebagai perantara-NP, dengan asumsi hanya beberapa hipotesis "masuk akal"?

Berikut adalah kumpulan dari beberapa respons masalah antara P dan NPC:

• Anjak piutang
• Masalah isomorfisma: Grafik isomorfisma [tidak NPC kecuali ] (via @ Jeff Kinne), Grafik automorphism, Grup isomorfisma, automorphism, Cincin isomorfisma dan automorphism (via @Joshua Grochow)$\sum_2^p=\prod_2^p$
• Menghitung jarak rotasi antara dua pohon biner atau jarak balik antara dua triangulasi dari set titik planar yang sama (via @ David Eppstein)
• Masalah Turnpike dalam merekonstruksi titik-titik secara online dari jarak jauh (melalui @Suresh Venkat)
• Masalah yang muncul dari Konjektur Game Unik (via @Moritz)
• Disc Log Problem dan lain-lain yang terkait dengan asumsi kriptografi (via @ Jo Fitzsimons)
• Menentukan pemenang dalam game paritas (via @mashca)
• Menentukan siapa yang memiliki peluang tertinggi untuk memenangkan permainan stokastik (via @Peter Shor di MO)
• Masalah angka dalam kotak (via @Joshua Grochow)
• Kontrol agenda untuk turnamen eliminasi tunggal seimbang (via @virgi)
• Simpul triviality (via @JeffE)
• (Dengan asumsi NEXP ≠ EXP) versi empuk dari NEXP - masalah lengkap (via @ Yosua Grochow)
• Masalah dalam TFNP (via @Marcos Villagra)
• Intersecting Monotone SAT (via @ András Salamon)
• Masalah Ukuran Sirkuit Minimum (melalui @Eric Allender)
• Memutuskan apakah triangulasi 3-manifold yang diberikan adalah 3-bola (via @ Jo O'Rourke dan @ Peter Shor)
• Masalah Pemotongan Stok dengan jumlah panjang objek konstan (via @Suresh Venkat)
• Monotone Self-Duality (via @Danu)
• Planar Minimum Bisection (via @turkistany)
• Pigeonhole Subset Sum (via @ user834)
• Jumlah Root Square (via @JeffE)
• Memutuskan Apakah Grafik Mengakui Pelabelan yang Anggun (via @Oleksandr Bondarenko)
• Versi gap dari vektor terdekat dalam masalah kisi, GapCVP (melalui @MCH)$(\sqrt{n})$
• Masalah terbagi linier [dikenal sebagai -lengkap tetapi bukan NPC] (via @Oleksandr Bondarenko)$\gamma$
• Menemukan dimensi VC (via @Mohammad al Turkistany)
• Menemukan set dominasi minimum dalam sebuah turnamen (via @Mohammad al Turkistany)
• Planaritas yang berkelompok

Masalah favorit saya di kelas ini (saya akan mengatakannya sebagai masalah fungsional, tetapi mudah untuk berubah menjadi masalah keputusan dengan cara standar): hitung jarak rotasi antara dua pohon biner (setara, jarak balik antara dua triangulasi dari poligon cembung).

Masalah yang tidak disebutkan dalam daftar ini atau daftar MO adalah masalah turnpike. Diberikan multiset dari n (n-1) / 2 angka, setiap angka mewakili jarak antara dua titik pada garis, merekonstruksi posisi titik-titik asli.

Perhatikan bahwa apa yang membuat nontrivial ini adalah bahwa untuk angka tertentu d dalam multiset, Anda tidak tahu pasangan poin mana yang terpisah d unit.

Meskipun diketahui bahwa untuk setiap contoh yang diberikan hanya ada sejumlah solusi polinomial, tidak diketahui bagaimana cara menemukannya!

Jumlah yang persegi masalah akar: Mengingat dua urutan dan b 1 , b 2 , ... , b n bilangan bulat positif, adalah A : = Σ i $a_1, a_2, \dots, a_n$$b_1, b_2, \dots, b_n$ kurang dari, sama dengan, atau lebih besar dariB:=βi$A := \sum_i \sqrt{a_i}$ ?$B := \sum_i \sqrt{b_i}$

• Masalahnya memiliki algoritma -waktu yang sepele pada RAM yang sebenarnya — Hitung saja jumlahnya dan bandingkan! —Tapi ini tidak menyiratkan keanggotaan dalam P.$O(n)$

• Ada algoritma presisi terbatas yang jelas, tetapi tidak diketahui apakah jumlah polinomial bit presisi cukup untuk kebenaran. (Lihat http://maven.smith.edu/~orourke/TOPP/P33.html untuk detailnya.)

• Teorema Pythogoras menyiratkan bahwa panjang dari setiap kurva poligon yang simpul dan titik akhir bilangannya adalah jumlah akar kuadrat dari bilangan bulat. Dengan demikian, jumlah-of-akar masalah adalah melekat di beberapa masalah geometri komputasi planar, termasuk Euclidean minimum spanning pohon , Euclidean jalur terpendek , triangulations minimum-berat , dan TSP Euclidean . (Masalah Euclidean MST dapat diselesaikan dalam waktu polinomial tanpa menyelesaikan masalah jumlah akar, berkat struktur matroid yang mendasarinya dan fakta bahwa EMST adalah subgraf dari triangulasi Delaunay.)

• Ada adalah polinomial-waktu algoritma acak, karena Johannes Blömer , untuk memutuskan apakah dua jumlah yang sama. Namun, jika jawabannya tidak, algoritma Blömer tidak menentukan jumlah yang lebih besar.

• Versi keputusan dari masalah ini (Is ?) Bahkan tidak diketahui dalam NP. Namun, algoritma Blömer menyiratkan bahwa jika masalah keputusan adalah dalam NP, maka itu juga dalam co-NP. Dengan demikian, masalahnya tidak mungkin NP-lengkap.$A > B$

Berikut adalah daftar masalah yang mungkin atau mungkin tidak memenuhi syarat sebagai "cukup" berbeda. Dengan bukti yang sama seperti untuk Grafik Isomorfisme, jika ada di antaranya NP-lengkap, maka Hirarki Polinomial runtuh ke tingkat kedua. Saya tidak berpikir ada konsensus luas mengenai yang mana dari "seharusnya" ini di P.

• Grafik Automorfisme (tentukan apakah grafik memiliki automorfisme nontrivial). Mengurangi ke Grafik Isomorfisme, tetapi tidak diketahui (tidak terpikirkan?) Sebagai GI-keras.
• Kelompok Isomorfisme dan Automorfisme (di mana kelompok diberikan oleh tabel perkaliannya). Sekali lagi, kurangi menjadi Graph Isomorphism, tetapi tidak dianggap sebagai GI-hard.
• Ring Isomorphism dan Automorphism. Dalam arti tertentu, ini adalah ayah dari semua masalah di atas, karena anjak bilangan bulat setara dengan menemukan automorfisme nontrivial dari sebuah cincin, dan Grafik Isomorfisme direduksi menjadi Isomorfisme Cincin. Lihat Neeraj Kayal, Nitin Saxena. Kompleksitas Masalah Cincin Morfisme. Kompleksitas Komputasi 15 (4): 342-390 (2006). (Menariknya, menentukan apakah cincin memiliki automorfisme nontrivial ada dalam )$P$
• Posting ini oleh Bill Gasarch berisi beberapa masalah lain dengan selera teori Ramsey yang terlihat seperti sedang.
• Dengan Teorema Mahaney, tidak ada set yang jarang yang bisa lengkap NP. Tapi kita juga tahu bahwa ada set jarang di - P IFF N E X P tidak sama dengan E X P . Jadi dengan asumsi N E X P $NP$$P$$NEXP$$EXP$ , versi empuk dari setiap N E X P -lengkapan lengkap adalah kompleksitas menengah. (Set seperti itu tidak bisa dalam P kecuali N E X P = E X $NEXP \neq EXP$$NEXP$$P$$NEXP = EXP$, Bertentangan asumsi kita.) Ada banyak alami masalah -Lengkap.$NEXP$

Minimum Circuit Size Problem (MCSP) adalah masalah "alami" favorit saya di NP yang tidak dikenal sebagai NP-complete: Mengingat tabel kebenaran (ukuran n = 2 ^ m) dari fungsi m-variate Boolean f, dan diberi angka s, apakah f memiliki sirkuit ukuran s? Jika MCSP mudah, maka tidak ada fungsi satu arah yang aman secara kriptografis. Masalah ini dan variannya memberikan banyak motivasi untuk studi tentang algoritma "brute-force" di Rusia, yang mengarah ke karya Levin tentang kelengkapan NP. Masalah ini juga dapat dilihat dalam hal kompleksitas Kolmogorov yang terbatas sumber daya: menanyakan apakah string dapat dipulihkan dengan cepat dari deskripsi singkat. Versi masalah ini dipelajari oleh Ko; nama MCSP pertama kali digunakan oleh Cai dan Kabanets, sejauh yang saya tahu. Lebih banyak referensi dapat ditemukan di beberapa makalah saya: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Dualitas diri monoton

Untuk fungsi boolean $f=f(x_1, x_2, ..., x_n)$ , itu ganda adalah $f^d=\bar{f}(\bar{x_1}, \bar{x_2}, ..., \bar{x_n})$ . Mengingat $f(x_1, x_2, ..., x_n)$diwakili oleh rumus CNF, kita harus memutuskan apakah $f=f^d$ .

Masalah ini ada di dalam co-NP [ $\log^2 n$ ], yaitu, dapat di decidable dengan $O(\log^2n/ \log\log n)$ langkah nondeterministic. Dengan demikian, ia memiliki algoritma waktu kuasi-polinomial ( $O(n^{\log n/\log \log n})$), dan karenanya tidak mungkin co-NP-hard.

Masih terbuka apakah masalah ini dalam P atau tidak. Rincian lebih lanjut dapat ditemukan di makalah 2008 " Aspek komputasi dualisasi monoton: Sebuah survei singkat " oleh Thomas Eiter, Kazuhisa Makino, dan Georg Gottlob.

Simpul sepele: Diberikan rantai poligon tertutup dalam 3-ruang, apakah tidak terpotong (yaitu ambient-isotop ke lingkaran datar)?

Ini dikenal sebagai NP oleh hasil mendalam dalam teori permukaan normal, tetapi tidak ada algoritma waktu-poli atau bukti kekerasan NP yang diketahui.

Tidak diketahui apakah mungkin untuk memutuskan dalam waktu polinomial apakah pemain 1 memiliki strategi kemenangan dalam permainan paritas (dari posisi awal yang diberikan). Masalahnya, bagaimanapun, terkandung dalam NP dan co-NP dan bahkan dalam UP dan co-UP.

Anda mendapatkan daftar masalah yang sangat panjang jika bersedia menerima masalah perkiraan, seperti perkiraan Max-Cut dalam faktor 0,878. Kami tidak tahu apakah itu NP-hard atau P (hanya tahu NP-hardness dengan asumsi Uniuqe Games Conjecture).

Dalam formula CNF monoton setiap klausa hanya berisi literal positif atau hanya literal negatif. Dalam rumus CNF monoton berpotongan setiap klausa positif memiliki beberapa variabel yang sama dengan setiap klausa negatif.

Masalah keputusan

INTERSECTING MONOTONE SAT
Input: berpotongan rumus CNF monoton Pertanyaan: apakah f memuaskan?$f$
$f$

memiliki algoritma sejak tahun 1996, tetapi tidak diketahui berada dalam P. (Tentu saja, itu mungkin berubah menjadi P, tetapi itu akan menjadi hasil utama.)$n^{o(\log\ n)}$

• Thomas Eiter dan Georg Gottlob, Perhitungan Transversal Hypergraph dan Masalah Terkait dalam Logika dan AI , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53

Apakah triangulasi 3-manifold diberikan 3-bola? Dari Joe O'Rourke.

Versi Pigeonhole dari Subset Sum (atau Subset Sum Equality).

Diberikan:

$S_1, S_2 \subseteq \{ 1, \dots, n \}$

Masalah jumlah subset pigeonhole meminta solusi seperti itu. Awalnya dinyatakan dalam " Algoritme pendekatan yang efisien untuk masalah kesetaraan SUBSET-SUMS " oleh Bazgan, Santha dan Tuza.

Ada banyak masalah terkait dengan menemukan subkelompok tersembunyi. Anda menyebutkan anjak piutang, tetapi ada juga masalah log diskrit serta yang lain terkait dengan kurva eliptik, dll.

Berikut adalah masalah dalam pilihan sosial komputasi yang tidak diketahui berada di P, dan mungkin atau mungkin tidak lengkap NP.

Kontrol agenda untuk turnamen eliminasi tunggal seimbang:

$T$$n=2^k$$a$

Pertanyaan: apakah ada permutasi node ( braket ) sehingga a adalah pemenang dari turnamen eliminasi tunggal yang diinduksi?

$P_k$$2^k$$V$$T$$V$$P_{k-1}$$2^{k-1}$$i>0$$P_k[2i-1]$$P_k[2i]$$e$$T$$P_{k-1}[i]=P_k[2i-1]$$e=(P_k[2i-1],P_k[2i])$$P_{k-1}[i]=P_k[2i]$$P_k$$T$$P_{k-1}$$2^k$$k$$P_{k-1},\ldots,P_0$$2^k$

Kontrol agenda untuk turnamen eliminasi tunggal seimbang (perumusan grafik):

$T$$n=2^k$$a$

$T$$2^k$$a$

$2^k$$x$$a$$2^{k-1}$$x$$2^{k-1}$$y$$x$$y$$k=0$

Beberapa referensi:

1. Jérôme Lang, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh: Penentuan Pemenang dalam Pemilihan Suara Berurutan. IJCAI 2007: 1372-1377.
2. N. Hazon, PE Dunne, S. Kraus, dan, M. Wooldridge. Bagaimana Rig Pemilihan dan Kompetisi. COMSOC 2008.
3. Thuc Vu, Alon Altman, Yoav Shoham. Pada kompleksitas masalah kontrol jadwal untuk turnamen sistem gugur. AAMAS (1) 2009: 225-232.
4. V. Vassilevska Williams. Memperbaiki turnamen. AAAI 2010.

Lihatlah TFNP kelas . Ini memiliki banyak masalah pencarian dengan status perantara.

Masalah isomorfisma subgraph yang diinduksi memiliki "pembatasan sisi kiri" NP-tidak lengkap dengan asumsi bahwa P tidak sama dengan NP. Lihat Y. Chen, M. Thurley, M. Weyer: Memahami Kompleksitas Isomorfisme Subgraph yang diinduksi , ICALP 2008.

$NP$$NP$

Masalah Bisection Minimum: Cari partisi set node menjadi dua bagian dengan ukuran yang sama sehingga jumlah sisi yang menyeberang diminimalkan.

Karpinski, Perkiraan Masalah Bisection Minimum: Sebuah Tantangan Algoritma

Pemotongan stok masalah dengan jumlah panjang objek yang konstan. Lihat diskusi ini untuk informasi lebih lanjut.

$n$$v$$1$$v$$\beta$$v$$\beta > 1$

$\beta = \sqrt{n}$$\mathsf{NP} \cap \mathsf{coNP}$$\mathsf{NP}$$\mathsf{P}$$\beta$$\beta = n^{o(1/\log \log n)}$$\mathsf{NP}$

$G = (V,E)$$f$$v\in V$$f(v)$$e = uv\in E$$|f(u) − f(v)|$$f : V\rightarrow \{0, 1, 2,\dots, |E|\}$$\{1, 2,..., |E|\}$

1. JA Gallian. Survei dinamis pelabelan grafik. The Electronic Journal of Combinatorics, 2009.
2. DS Johnson. Kolom NP-kelengkapan: Panduan yang sedang berlangsung. J. Algorithms, 4 (1): 87–100, 1983.
3. DS Johnson. Kolom NP-kelengkapan. Transaksi ACM tentang Algoritma, 1 (1): 160–176, 2005.

$P$$NP$$O(n^{\log n})$$NP$$NP$

$a$$b$$a \cdot x+1$$b$

$\gamma$

Garey dan Johnson dalam "Komputer dan Ketidaktertaruhan" mani mengatakan bahwa (hlm. 158-159):

$\gamma$$R_M$$M$

$$R_M=\{\langle x,y\rangle:there\ is\ a\ string\ z\ such\ that\ on\ input\ x\ and\ guess\ z\ M\ has\ output\ y\}$$

$L_1$$\Sigma_1$$\gamma$$L_2$$\Sigma_2$$L_1\propto_{\gamma}L_2$$M$$x\in\Sigma_1^*$$y\in\Sigma_2^*$$\langle x,y\rangle\in R_M$$\langle x,y\rangle\in R_M$$x\in L_1$$y\in L_2$$M$$x$$x$$x$$L_2$$x\in L_1$

$P$$NP$$O(n^{\log n})$

Masalah berikut ini diyakini sebagai NP-Menengah, yaitu di NP tetapi tidak di P atau NP-lengkap.

Memecahkan Masalah Root Polinomial (EPRP)

$p(x)$$\deg(p) \geq 0$$GF(q)$$q$$r$

$\deg(p)=0$

Untuk detail tambahan, lihat pertanyaan saya dan diskusi terkait .

Saya tidak tahu apakah masalah isomorfisme hypergraph tertimbang yang diajukan dalam jawaban oleh Thinh D. Nguyen tidak bisa hanya ditunjukkan sebagai GI lengkap. Namun, ada masalah GI-hard terkait erat dengan GI, yang belum direduksi menjadi GI, yaitu masalah string isomorphism (juga disebut masalah color isomorphism ). Ini adalah masalah yang sebenarnya ditunjukkan dalam waktu kuasi-polinomial oleh László Babai. Ini adalah kepentingan independen, karena itu setara dengan sejumlah masalah keputusan dalam teori grup (permutasi):

• masalah persimpangan coset
• masalah pengujian keanggotaan coset ganda
• masalah faktorisasi kelompok

Masalah yang tidak diketahui berada dalam FP atau NP-hard adalah masalah menemukan pohon Steiner minimal ketika simpul Steiner dijanjikan akan jatuh pada dua segmen garis lurus berpotongan pada sudut 120 °. Jika sudut antara segmen garis kurang dari 120 °, maka masalahnya adalah NP-hard. Dugaan bahwa ketika sudut lebih besar dari 120 °, maka masalahnya adalah pada FP.

Karenanya masalah keputusan berikut saat ini tampaknya memiliki kompleksitas menengah:

$q$
$q$

Tentu saja, ini mungkin benar-benar dalam P atau NP-lengkap, tetapi kemudian tampaknya kita akan memiliki dikotomi yang menarik pada 120 ° bukannya masalah menengah. (Dugaan itu mungkin juga salah.)

• JH Rubinstein, DA Thomas, NC Wormald, Steiner Trees for Terminals Constrained to Curves , SIAM J. Discrete Math. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190

$G_1$$G_2$$n$$\pi$$G_1$$G_2$$NP$