Timeline for Problems Between P and NPC
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 24, 2017 at 19:11 | comment | added | Mark S | Since the time this answer was first posted, Kuperberg placed it in $\mathsf{coNP}$ conditional on the Generalized Riemann Hypothesis, and Lackenby placed it unconditonally in $\mathsf{coNP}$. | |
| Oct 29, 2010 at 5:55 | comment | added | Jeffε | Actually, that's still open. Tasos Sidiropoulos found a bug in the Hara-Tani-Yamamoto proof. | |
| Oct 29, 2010 at 4:13 | comment | added | Peter Shor | It's also contained in co-AM (Hara, Tani, Yamamoto), so not NPC unless the polynomial hierarchy collapses. | |
| Oct 25, 2010 at 2:45 | comment | added | Joshua Grochow | It might be worth mentioning that, as with many potentially NP-intermediate problems, a slight variant is known to be NP-complete. Namely, 3-manifold knot genus is NP-complete: given a closed polygonal chain in a triangulated 3-manifold and an integer g, is the knot the boundary of a surface of genus at most g? (Being the unknot is equivalent to genus 0.) doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016 | |
| Sep 9, 2010 at 1:16 | history | answered | Jeffε | CC BY-SA 2.5 |