Apakah ada rumusan teori simpul masalah NP lengkap?

Apakah ada masalah NP lengkap (atau bahkan NP-keras, atau NP) yang memiliki sifat topologi yang baik untuk dipelajari. Apakah masalah NP memiliki formulasi teori simpul? Kita tahu tentang hasil # tentang polinomial Jones. Masalah grafik (embeddings?), Khususnya pewarnaan grafik dapat dilihat memiliki sifat teori simpul yang bagus. Ini adalah pertanyaan terbuka, dan segala referensi untuk topik ini sangat dihargai. $P$

ct.category-theory np pengguna3483902
sumber

Jawaban:

Anda dapat melihat ke:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac, dan Aleksandar Chakarov. 2009. Torus knot tiga warna NP-lengkap . Dalam Prosiding Konferensi Regional Tenggara Tahunan ke-47 (ACM-SE 47). ACM, New York, NY, AS,, Artikel 42, 6 halaman.

Abstrak: Karya ini menyajikan metode untuk menghubungkan kelas masalah kepuasan kendala untuk simpul tiga dimensi. Diberi simpul, seseorang dapat membangun simpul quandle, yang umumnya merupakan aljabar bebas tanpa batas. Kumpulan masalah yang diinginkan berasal dari serangkaian hubungan invarian atas simpul quandle, menerapkan teori yang mengaitkan aljabar terbatas dengan kendala masalah kepuasan. Hal ini memungkinkan kami untuk mengembangkan gagasan tentang quandle dan knot yang dapat diselesaikan dengan NP dan lengkap. Secara khusus, kami menunjukkan bahwa semua simpul torus tricolorable dan semua kecuali paling banyak 2 simpul non-sepele dengan 10 atau lebih sedikit penyeberangan adalah NP-lengkap.

dan juga untuk laporan mani:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac, dan J. Wood. Kelas masalah kepuasan kendala atas simpul . Nomor Laporan Teknis BARD-CMSC-2008-01, Bard College, 2008.

Marzio De Biasi
sumber

Ada beberapa referensi dalam paragraf pertama

Marc Lackenby. Batas atas polinomial pada gerakan Reidemeister arXiv: 1302.0180

$\mathbf{NP} \cap \mathbf{coNP}$

Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. Kompleksitas Komputasi Masalah Simpul dan Tautan. J. ACM 46 (1999) 185-211. arXiv: matematika / 9807016
Greg Kuperberg. Ketertarikan dalam NP, modulo GRH. Desember 2011, revisi Januari 2014. arXiv: 1112.0845

$g$

Ian Agol, Joel Hass, William Thurston. 3-MANIFOLD KNOT GENUS adalah NP-complete. STOC 2002. Tautan ACM

Saya tertarik pada contoh lain juga.

Noam Zeilberger
sumber

Bukti co-NP dari Agol yang menggunakan hierarki dijahit diringkas secara singkat dalam survei terbaru Lackenby: people.maths.ox.ac.uk/lackenby/ekt11214.pdf

Arnaud

R^{3}

$\mathbb{R}^3$

R^{3}

$\mathbb{R}^3$

S^{3}

$\mathbb{S}^3$

terima kasih atas ketepatan Anda: Saya sudah memasukkannya ke dalam teks.

Noam Zeilberger

Mungkin padat di sini, tetapi tidak jelas mengapa hasilnya dicirikan dalam jawaban yang berbicara tentang kesimpitan / ketidakberesan "menjadi NP-hard", daripada "berada di NP", karena sejauh yang saya bisa lihat dalam abstrak, mereka menegaskan bahwa masalahnya adalah dalam NP, tetapi tidak bahwa mereka NP-Lengkap juga.

Abel Molina

tidak, Anda benar, saya hanya menjadi padat. Diperbaiki sekarang

Noam Zeilberger