Timeline for What are the most important results (and papers) in complexity theory that every one should know?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 7, 2010 at 14:27 | comment | added | Robin Kothari | Also BQPSPACE=PSPACE. | |
| Aug 6, 2010 at 2:22 | comment | added | Marcos Villagra | Thanks for the info. But what I wanted to point out is that for the "lower" classical complexity classes (PSPACE and below) this is the best, is that correct? Although the NQP=coC_{=}P result seems to be at a really low level. | |
| Aug 6, 2010 at 1:31 | comment | added | Scott Aaronson | Two corrections: first, there were several previous results that completely characterized a quantum complexity class in terms of a classical class (for example, QRG=EXP, NQP=coC_{=}P, PostBQP=PP, and BQP_CTC=PSPACE). Second, while PSPACE in QIP is nonrelativizing, the "new" direction (QIP in PSPACE) is relativizing. | |
| Aug 5, 2010 at 23:29 | comment | added | Marcos Villagra | Well, I have a bias here to be honest but I propose this as a result for the 2005-2010 period. First, to my knowledge, this is the best relation we have between classical and quantum classes. There are other good results on upper bounds for BQP, but this is the only result where a quantum complexity class is completely characterized. Second, although I don't know the complete details, the proof seems to be non-relativizing. And that's important because we can try to learn from here and use it to proof other non-relativizing results. Although, other people already tried that. | |
| Aug 5, 2010 at 17:49 | comment | added | András Salamon | Is there a particular reason you chose this result? | |
| Aug 5, 2010 at 12:48 | history | answered | Marcos Villagra | CC BY-SA 2.5 |