Timeline for Dominations under oracles which is closed under complement?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 29, 2010 at 1:24 | comment | added | Tsuyoshi Ito | @Hsien-Chih Chang: Fenner, Fortnow, Kurtz and Li 2003 define a notion called “relativizable complexity class,” which is a mapping C which takes a language A to a complexity class C^A satisfying certain properties. This notion may be useful to make the original question (revision 1 or the question) rigorous without restricting the class C to a specific class. | |
| Nov 28, 2010 at 16:18 | comment | added | Hsien-Chih Chang 張顯之 | You are correct; I did not aware that $\mathsf{C^O}$ may be not well-defined. I'll try to modify my question, please correct me if it is still problematic. | |
| Nov 28, 2010 at 2:12 | history | answered | John Watrous | CC BY-SA 2.5 |