Timeline for Unambiguous SAT and sparse languages
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2017 at 20:00 | vote | accept | Turbo | ||
| Apr 28, 2017 at 19:01 | answer | added | Joshua Grochow | timeline score: 2 | |
| Apr 28, 2017 at 17:00 | comment | added | Turbo | @JoshuaGrochow yes I think allowing arbitrary answers for instances not satisfying promise is the right thing to do (is there another alternative?). But it seems to me that then it might trivialize the query. | |
| Apr 28, 2017 at 15:36 | comment | added | Joshua Grochow | UnambiguousSAT is a promise problem. When you say it reduces to a sparse language S, do you have in mind the usual thing of allowing the reduction to give arbitrary answers on instances that don't satisfy the promise (ie, which have more than one satisfying assignment)? | |
| Apr 27, 2017 at 17:32 | history | undeleted | Turbo | ||
| Apr 27, 2017 at 11:31 | history | deleted | Turbo | via Vote | |
| Apr 27, 2017 at 10:21 | history | asked | Turbo | CC BY-SA 3.0 |