Timeline for The Examiner's Problem (uniform generation of SAT decision instances/answers)
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2013 at 3:09 | vote | accept | usul | ||
| May 1, 2013 at 23:07 | comment | added | Sasho Nikolov | Each $M$ gives a tally language in NP: $L_M =\{1^n: M(1^n) \text{ is satisfiable.}\}$. So if unary-NP is equal to unary-P, then $M'$ is the machine that decides $L_M$. In the other direction, take any tally language in NP and take $M$ to be the machine that reduces it to SAT. If $M'$ exists, then the tally language is also in P, so unary P = unary NP. For the second equivalence you can check Hartmanis et al. (but one direction is very easy) dl.acm.org/citation.cfm?id=808769 | |
| May 1, 2013 at 17:41 | comment | added | usul | Can you explain why it is equivalent? ... By "uniform", I mean "uniform model of computation" -- if we asked the question for circuits, the answer would be trivially yes: each $M'_n$ would hardcode either a one or a zero, depending on whether $M_n$ is satisfiable or not. | |
| May 1, 2013 at 15:24 | history | answered | Manu | CC BY-SA 3.0 |