Timeline for Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2013 at 21:26 | comment | added | Joshua Grochow | @TayfunPay: Yes, if P=NP then VV can be done completely deterministically. My first point was just that if P=NP, then one can get the same effect as VV (isolating a witness) much easier than in VV itself. | |
| Jun 21, 2013 at 18:12 | comment | added | Tayfun Pay | Okay. Thank You for your reply. Little more. If ${\bf P} = {\bf NP}$ then ${\bf UP}$ would be in ${\bf P}$ so we could solve promise_UP in polynomial time since promise_UP is the class of promise problems solvable by an UP machine... Also if ${\bf P} = {\bf NP}$ then ${\bf RP}$ would be in ${\bf P}$ as well then this implies that Valiant Vazirani could be done in "deterministic" polynomial time? That is what I was getting at. Thank you | |
| Jun 21, 2013 at 3:00 | comment | added | Joshua Grochow | @TayfunPay: If P=NP, then you can just check if $\varphi$ is satisfiable, and if so output the formula $x_1 \wedge \dotsb \wedge x_n$ which clearly has a unique satisfying assignment, and otherwise output $x_1 \wedge \neg x_1$. In regards to your other questions, no, UP and PromiseUP are not interchangeable as oracles (cstheory.stackexchange.com/a/17494/129, cstheory.stackexchange.com/a/11171/129). To see why not, think about what UP language you would use as an oracle for Valiant-Vazirani. | |
| Jun 17, 2013 at 0:07 | comment | added | Tayfun Pay | Under the assumption that ${\bf P} = {\bf NP}$, is it true that there exits a deterministic polynomial time algorithm such that given a SAT formula with x satisfying truth assignments we can get a formula with a unique satisfying truth assignment? That is does Valiant Vazirani reduction turn into a deterministic polynomial time reduction when ${\bf P} = {\bf NP}$? Also, isn't ${\bf UP}$ and ${Promise \bf UP}$ are interchangeable as oracles the same way ${\bf NP}$ and ${SAT}$ are interchangeable as oracles. | |
| Feb 8, 2013 at 16:59 | vote | accept | CommunityBot | ||
| Dec 17, 2012 at 8:13 | history | edited | Suresh Venkat | CC BY-SA 3.0 |
added 48 characters in body
|
| Dec 16, 2012 at 21:34 | history | answered | Joshua Grochow | CC BY-SA 3.0 |