Timeline for Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 20, 2010 at 3:43 | comment | added | Andy Drucker | That's a good point, and I hadn't thought about VV in quite those terms before (as talking about Promise-UP). Here by a randomized reduction to promise problem $\Pi$ we mean randomized reductions which work w.h.p. given any solver for $\Pi$; we can't insist that the solver only be fed instances obeying the promise $\Pi$, since in VV we expect some instances with non-unique solutions. | |
| Aug 20, 2010 at 1:24 | comment | added | Joshua Grochow | Very interesting! I think the "technicality" of promise classes is very relevant, though. For example, Valiant-Vazirani shows that PromiseUP is NP-hard under randomized reductions, yet I doubt any such thing is true for UP. (Indeed, if VV can be derandomized and this were true, then we would have NP=UP. Of course, there aren't many known bad consequences of NP=UP, but it seems quite unlikely.) | |
| Aug 19, 2010 at 21:23 | history | edited | Andy Drucker | CC BY-SA 2.5 |
fixed math typo
|
| Aug 19, 2010 at 21:17 | history | answered | Andy Drucker | CC BY-SA 2.5 |