Timeline for Canonical representation of Binary Decision Tree in Ptime?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 19, 2015 at 23:15 | history | bounty ended | CommunityBot | ||
| S Nov 19, 2015 at 23:15 | history | notice removed | CommunityBot | ||
| S Nov 11, 2015 at 21:30 | history | bounty started | Marc | ||
| S Nov 11, 2015 at 21:30 | history | notice added | Marc | Improve details | |
| Aug 1, 2015 at 8:48 | review | Suggested edits | |||
| Aug 1, 2015 at 14:50 | |||||
| Jul 17, 2015 at 9:34 | history | edited | Marc | CC BY-SA 3.0 |
added 97 characters in body
|
| Jul 16, 2015 at 15:57 | comment | added | Marc | I agree, that was confusing, sorry. Either way I'd be also interested in an impossibility for only 1&2. And $Ker\neq CF$ is also left open at the end of their article. | |
| Jul 16, 2015 at 14:26 | comment | added | user6973 | However, it's far from clear to me that the impossibility of fulfilling 1&2&3 implies $\: PEq \neq Ker \;$. $\:\:$ | |
| Jul 16, 2015 at 14:00 | comment | added | Marc | The equivalence of BDT $\sim$ is in $PEq$. So if it is not in $Ker$ (ie. it is impossible to find $f$ fulfilling 1,2) we have an example of an equivalence relation living in $PEq\setminus Ker$. If we can fulfil 1,2 but not 3 then it is in $Ker\setminus CF$ ($CF$ being the class with canonical forms, stronger than invariants) etc. | |
| Jul 16, 2015 at 13:39 | comment | added | user6973 | Why would a "negative answer to this question" "provide a separation result $PEq \neq Ker$"? $\hspace{.49 in}$ | |
| Jul 16, 2015 at 13:34 | history | edited | Marc | CC BY-SA 3.0 |
Include feedback in comments and progress on the question.
|
| Jul 8, 2015 at 7:24 | comment | added | Marc | Thank you Ricky Demer, I did not know a systematic approach to this question existed. | |
| Jul 7, 2015 at 13:24 | history | tweeted | twitter.com/#!/StackCSTheory/status/618410276635955200 | ||
| Jul 7, 2015 at 0:07 | answer | added | William Hoza | timeline score: 9 | |
| Jul 6, 2015 at 23:32 | comment | added | William Hoza | @RickyDemer: Yes, ~ can be decided in polynomial time. | |
| Jul 6, 2015 at 19:46 | comment | added | user6973 | Independently of that, your question is equivalent to "Does $\sim$ have an FP canonical form?". $\hspace{.54 in}$ | |
| Jul 6, 2015 at 19:31 | comment | added | user6973 | Is $\sim$ even known to be in Ptime? $\;$ | |
| Jul 6, 2015 at 18:55 | history | asked | Marc | CC BY-SA 3.0 |