Timeline for Dominations under oracles which is closed under complement?
Current License: CC BY-SA 2.5
14 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/
|
|
| Dec 20, 2010 at 12:14 | vote | accept | Hsien-Chih Chang 張顯之 | ||
| Nov 29, 2010 at 6:18 | comment | added | Kaveh | It is not open for all of them, it is well-known that the two reductions are not equivalent for some large classes. | |
| Nov 28, 2010 at 20:04 | answer | added | Tsuyoshi Ito | timeline score: 7 | |
| Nov 28, 2010 at 17:35 | comment | added | Hsien-Chih Chang 張顯之 | Is it open for every class $\mathsf{O}$, or known to be the same for some specific classes? If the latter is true, I would like to know any criterion to $\mathsf{O}$ to make these two notions equal. | |
| Nov 28, 2010 at 17:26 | comment | added | Kaveh | If $O$ is not closed under log-space Turing reductions then this still holds and there are such $O$, so you may want to state that $O$ is closed under composition at least, in which case I think the question becomes "is log-space Turing reductions the same as log-space many-one reductions?" which is probably open. | |
| Nov 28, 2010 at 17:19 | comment | added | Hsien-Chih Chang 張顯之 | We need that $\mathsf{L} \subseteq \mathsf{O}$, as stated in line 4. Sorry for the unclarity... | |
| Nov 28, 2010 at 17:16 | comment | added | Kaveh | For the second question, sure, e.g. take $O$ to be the empty set. | |
| Nov 28, 2010 at 17:12 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |
added 123 characters in body
|
| Nov 28, 2010 at 17:07 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |
C^O ill-defined, replace C with L
|
| Nov 28, 2010 at 2:12 | answer | added | John Watrous | timeline score: 10 | |
| Nov 26, 2010 at 16:46 | comment | added | Hsien-Chih Chang 張顯之 | We do have $\mathsf{P^P} = \mathsf{P}$ and $\mathsf{EXP^{EXP}} \neq \mathsf{EXP}$; it seems that one needs to be able to simulate an $\mathsf{O}$-oracle call in $\mathsf{O}$ at least. But I do not know any conditions that can guarantee the equality holds i.e. $\mathsf{O^O} = \mathsf{O}$ when $\mathsf{C} = \mathsf{O}$. | |
| Nov 26, 2010 at 16:04 | comment | added | András Salamon | Do you know anything about the extremal case where $C = O$? | |
| Nov 26, 2010 at 8:45 | history | asked | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |