Timeline for Complete problems for randomized complexity classes
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Feb 4, 2013 at 14:38 | answer | added | Oded Goldreich | timeline score: 6 | |
| Aug 4, 2010 at 13:00 | vote | accept | Marcos Villagra | ||
| Aug 4, 2010 at 6:18 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
edited body
|
| Aug 4, 2010 at 4:14 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
added 7 characters in body
|
| Aug 4, 2010 at 4:14 | comment | added | Marcos Villagra | Yes, it actually should read "there exists" instead of "for any". | |
| Aug 4, 2010 at 3:51 | comment | added | Tsuyoshi Ito | As I wrote, I do not think that it is believed that BPP has no complete language. I am afraid that there is also something wrong with the second sentence because BPP^PSPACE=PSPACE has a complete language. I do not know the situation about MA, though. At least, I believe that no MA-complete language is known, because such a characterization of MA would be a huge discovery. | |
| Aug 4, 2010 at 3:46 | answer | added | Ryan Williams | timeline score: 20 | |
| Aug 4, 2010 at 3:45 | answer | added | Peter Shor | timeline score: 22 | |
| Aug 4, 2010 at 3:39 | history | edited | Marcos Villagra | CC BY-SA 2.5 |
added 44 characters in body
|
| Aug 4, 2010 at 3:35 | comment | added | Marcos Villagra | Yes, that's true. It is a very strong thig to say. I'll edit that part. Thanks | |
| Aug 4, 2010 at 3:19 | comment | added | Tsuyoshi Ito | Actually, it is not clear that BPP has no complete language. In fact, some (many?) complexity theorists believe BPP=P, in which case BPP has a complete language! | |
| Aug 4, 2010 at 2:51 | history | asked | Marcos Villagra | CC BY-SA 2.5 |