Timeline for Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?
Current License: CC BY-SA 3.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Feb 3, 2014 at 5:02 | comment | added | vzn | oh MAT cites Schaefer dichotomy thm / wikipedia. so more specifically, are there any other thms that are known to be similar to that one? | |
| Feb 1, 2014 at 19:00 | vote | accept | Mohammad Al-Turkistany | ||
| Feb 1, 2014 at 18:08 | comment | added | vzn | this question seems to allude to a "dichotomy thm" analog possibly from somewhere else; are there any examples of other "dichotomy thms" along these lines in the literature? | |
| Jan 31, 2014 at 23:51 | answer | added | Joshua Grochow | timeline score: 7 | |
| Jan 30, 2014 at 20:20 | comment | added | David Eppstein | The restriction to NP problems does nothing to prevent examples such as the GI-complete one in my answer. | |
| Jan 30, 2014 at 18:17 | comment | added | Mohammad Al-Turkistany | @Kaveh I'll miss you as an excellent moderator. Thanks for your service. | |
| Jan 30, 2014 at 17:18 | comment | added | Kaveh | @Mohammad, I removed CW flag, please be more careful with your future edits so it doesn't become CW automatically again. | |
| Jan 30, 2014 at 17:17 | history | wiki removed | Kaveh | ||
| Jan 30, 2014 at 13:00 | answer | added | David Richerby | timeline score: 5 | |
| Jan 30, 2014 at 12:28 | comment | added | David Richerby | Your edit seems to be restricting to properties that are already in NP. Also you don't need to exclude problems that have either a finite number of "yes" instances or a finite number of "no" instances because any such problem is trivially in P so could not be a counterexample to your proposed dichotomy. | |
| Jan 30, 2014 at 11:06 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 10 characters in body
|
| Jan 30, 2014 at 10:05 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 572 characters in body
|
| Jan 30, 2014 at 8:21 | answer | added | David Richerby | timeline score: 3 | |
| Jan 30, 2014 at 7:42 | answer | added | David Eppstein | timeline score: 11 | |
| Jan 30, 2014 at 4:32 | history | tweeted | twitter.com/#!/StackCSTheory/status/428747488603148288 | ||
| Jan 30, 2014 at 3:15 | comment | added | Mohammad Al-Turkistany | @JoshuaGrochow Thanks for your comment. I hope that the four examples I gave would provide "working" definition of natural interesting property of cubic graphs. Personally, I conjecture that deciding any natural interesting property of cubic graphs is $NP$-complete. | |
| Jan 30, 2014 at 3:04 | comment | added | Joshua Grochow | Interesting question! But in order to get a dichotomy theorem I think one would have to pick a defn of "natural interesting property." Maybe isomorphism-invariant is enough (all your examples are, and I would think all natural examples ought to be), despite the fact that surely some iso-invariant properties might not seem "natural." A P/NP-hard dichotomy for iso-invariant properties of cubic graphs would be a very interesting theorem. (I say NP-hard and not NPC b/c one can probably cook up an iso-invariant property that is, e.g., PSPACE-complete by considering some game on the graph.) | |
| Jan 30, 2014 at 2:52 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 10 characters in body
|
| Jan 30, 2014 at 2:32 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 265 characters in body
|
| Jan 30, 2014 at 2:26 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 265 characters in body
|
| Jan 30, 2014 at 2:11 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 3 characters in body
|
| Jan 30, 2014 at 1:56 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 3 characters in body
|
| Jan 29, 2014 at 23:14 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 7 characters in body
|
| Jan 29, 2014 at 22:44 | comment | added | Mohammad Al-Turkistany | Although the following does not answer the above question, I am interested in polynomial-time decidable natural interesting properties of cubic graphs. If no such examples exist, It is natural to conjecture that deciding any natural interesting property of cubic graphs is $NP$-complete. | |
| Jan 29, 2014 at 22:38 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 44 characters in body
|
| Jan 29, 2014 at 22:25 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 74 characters in body
|
| Jan 29, 2014 at 22:16 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 386 characters in body
|
| Jan 29, 2014 at 21:52 | history | asked | Mohammad Al-Turkistany | CC BY-SA 3.0 |