Timeline for Problems Between P and NPC
Current License: CC BY-SA 4.0
51 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2020 at 14:46 | comment | added | Hsien-Chih Chang 張顯之 | Removed the entry clustered planarity, which has been shown to be in P recently. | |
| Aug 14, 2020 at 14:44 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 4.0 |
deleted 88 characters in body
|
| S Aug 11, 2020 at 16:19 | history | suggested | CommunityBot | CC BY-SA 4.0 |
Added convexity assumption for flip distance (otherwise the problem is NPC, even APX-Hard, see A. Pilz "Flip distance between triangulations of a planar point set is APX-hard")
|
| Aug 7, 2020 at 16:42 | review | Suggested edits | |||
| S Aug 11, 2020 at 16:19 | |||||
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Nov 13, 2015 at 20:31 | history | edited | David Eppstein | CC BY-SA 3.0 |
Remove matching preclusion
|
| Aug 3, 2015 at 3:04 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
added dominating sets in tournaments
|
| Nov 23, 2013 at 17:13 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
vc dim
|
| Nov 15, 2013 at 21:40 | history | edited | David Eppstein | CC BY-SA 3.0 |
add matching preclusion
|
| Aug 20, 2011 at 14:45 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
added linear divisibility
|
| Aug 20, 2011 at 14:37 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
formatting
|
| Aug 17, 2011 at 20:49 | history | edited | Mahdi Cheraghchi | CC BY-SA 3.0 |
added 93 characters in body
|
| Aug 9, 2011 at 20:44 | comment | added | Joshua Grochow | @Timothy Chow: The example above assuming $NEXP \neq EXP$ is provably intermediate, that is, assuming $NEXP \neq EXP$, the padded version of a $NEXP$-complete problem is provably neither $NP$-complete by Mahaney nor in $P$, as that would contradict $NEXP \neq EXP$. | |
| Aug 9, 2011 at 19:42 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
added 55 characters in body
|
| Aug 8, 2011 at 22:18 | comment | added | Kaveh | @Lev, maybe you should edit the question to include Timothy's comments since it is less likely that people will see it here. | |
| Jun 30, 2011 at 19:59 | comment | added | Jeff KInne | @Timothy Chow, @Lev Reyzin. Graph isomorphism is not NP-complete unless $\Sigma_2^p = \Pi_2^p$, because graph non-isomorphism is in AM, and coNP in AM implies $\Sigma_2^p = \Pi_2^p$. This would work for other problems whose complements are in AM. This of course does not rule out GI being in P. | |
| Jun 27, 2011 at 13:38 | comment | added | Lev Reyzin♦ | @Timothy Chow, that's a good question, and it would be useful information to have in this list. Anyhow who knows should feel free to edit this answer with the relevant details. | |
| Jun 25, 2011 at 17:57 | comment | added | Timothy Chow | Are any of these examples provably NP-intermediate, assuming only some "reasonable" hypothesis (i.e., a hypothesis less trivial than "this problem is NP-intermediate")? If so, it would be interesting to mention that in this list. | |
| May 25, 2011 at 1:08 | vote | accept | Lev Reyzin♦ | ||
| May 24, 2011 at 5:31 | history | edited | Lev Reyzin♦ | CC BY-SA 3.0 |
added graceful labeling
|
| S Feb 25, 2011 at 7:03 | history | suggested | Bob Fraser | CC BY-SA 2.5 |
Removed Planar MAX 2-SAT, known to be NPC
|
| Feb 24, 2011 at 21:51 | review | Suggested edits | |||
| S Feb 25, 2011 at 7:03 | |||||
| Feb 24, 2011 at 21:50 | comment | added | Bob Fraser | I'm removing Planar MAX 2-SAT from the list, it was shown to be NP-complete by Guibas et al. in "Approximating polygons and subdivisions with minimum link paths" (springerlink.com/content/y234m35416w043v1) | |
| Dec 29, 2010 at 14:09 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |
Square Root Sums
|
| Dec 28, 2010 at 22:24 | history | edited | David Eppstein | CC BY-SA 2.5 |
add flip distance to rotation distance bullet
|
| Dec 28, 2010 at 21:05 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
planar min/max 2-sat
|
| Dec 26, 2010 at 4:09 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
planar min bisection
|
| Dec 23, 2010 at 14:10 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
monotone self duality
|
| Dec 19, 2010 at 13:29 | history | edited | Mohammad Al-Turkistany | CC BY-SA 2.5 |
deleted 34 characters in body
|
| Dec 18, 2010 at 0:51 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added 28 characters in body
|
| Dec 17, 2010 at 17:34 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added factoring reference; added 15 characters in body
|
| Oct 26, 2010 at 21:22 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
3 manifold
|
| Sep 28, 2010 at 14:05 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
MCSP
|
| Sep 28, 2010 at 2:14 | vote | accept | Lev Reyzin♦ | ||
| May 25, 2011 at 1:08 | |||||
| Sep 28, 2010 at 2:10 | vote | accept | Lev Reyzin♦ | ||
| Sep 28, 2010 at 2:13 | |||||
| Sep 27, 2010 at 21:33 | comment | added | András Salamon | It would be great to be able to add an answer to one's watchlist. This would definitely be on mine. | |
| Sep 27, 2010 at 21:27 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
intersecting monotone sat
|
| Sep 27, 2010 at 18:05 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added tfnp
|
| Sep 22, 2010 at 14:35 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added nexp-complete
|
| Sep 9, 2010 at 12:52 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added knot triviality
|
| Sep 9, 2010 at 0:06 | comment | added | Suresh Venkat | Yes, this procedure works, as the "official" answer. | |
| Aug 26, 2010 at 20:07 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added agenda control to list
|
| Aug 24, 2010 at 22:06 | comment | added | Lev Reyzin♦ | @Jukka Sounds good. I'll try to keep the list updated. | |
| Aug 24, 2010 at 9:46 | comment | added | Jukka Suomela | @Lev: This is perfect if you keep the summary updated. Then we can upvote this and it'll stay near the top. | |
| Aug 19, 2010 at 4:08 | comment | added | Lev Reyzin♦ | I made this the "accepted answer" as it combines all of the answers herein. Making this answer a part of the question seems strange, but I don't object to doing that... I know it's kinda weird for me to make "my" answer the accepted one. I welcome opinions on whether I should change it. | |
| Aug 19, 2010 at 4:07 | vote | accept | Lev Reyzin♦ | ||
| Sep 28, 2010 at 2:10 | |||||
| Aug 19, 2010 at 2:52 | comment | added | Joshua Grochow | I don't know what the community wiki etiquette is here, but maybe this summary should be added as an addendum to the question statement? | |
| Aug 18, 2010 at 15:39 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added reference
|
| Aug 18, 2010 at 15:31 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
added stochastic games
|
| Aug 18, 2010 at 15:26 | history | edited | Lev Reyzin♦ | CC BY-SA 2.5 |
capitalization made consistent
|
| Aug 18, 2010 at 4:09 | history | answered | Lev Reyzin♦ | CC BY-SA 2.5 |