Timeline for Unique SAT vs Exactly $m$ models
Current License: CC BY-SA 3.0
41 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2011 at 10:20 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 460 characters in body
|
| Nov 23, 2011 at 15:33 | vote | accept | Xavier Labouze | ||
| Nov 23, 2011 at 15:33 | vote | accept | Xavier Labouze | ||
| Nov 23, 2011 at 15:33 | |||||
| Oct 28, 2011 at 13:37 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 464 characters in body
|
| Oct 20, 2011 at 10:28 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 31 characters in body
|
| Oct 20, 2011 at 0:57 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 43 characters in body; Post Made Community Wiki
|
| Oct 19, 2011 at 6:45 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 332 characters in body
|
| Oct 9, 2011 at 19:08 | answer | added | Noam | timeline score: 13 | |
| Oct 9, 2011 at 14:52 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 149 characters in body
|
| Oct 8, 2011 at 13:05 | comment | added | Tsuyoshi Ito | Although you state that m is polynomially bounded, some of the statements in the question require m to be arbitrary and no longer hold if you constrain m to be polynomially bounded. You have to understand what you are talking about before you can ask a coherent question. This is why I do not want to post an answer to this question here, where questions are expected to be at research level. | |
| Oct 8, 2011 at 11:35 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 13 characters in body
|
| Oct 5, 2011 at 12:38 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Oct 5, 2011 at 12:36 | comment | added | Xavier Labouze | @Tsuyoshi : Please make your answering comment a full answer. | |
| Oct 5, 2011 at 12:30 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 809 characters in body
|
| Oct 3, 2011 at 13:04 | comment | added | Tsuyoshi Ito | It maps no-instances to no-instances (otherwise I would not call it a reduction). | |
| Oct 3, 2011 at 7:28 | comment | added | Xavier Labouze | @Tsuyoshi : (1) This reduction maps yes instances, what about no instances ? (2) tks for your concern. | |
| Oct 2, 2011 at 23:37 | comment | added | Tsuyoshi Ito | (1) If m is polynomially bounded, your problem is polynomial-time many-one reducible to Unique SAT by treating a list of m solutions sorted in the lexicographical order as a single certificate. (2) Please do not take my giving an answer as an evidence that you asked your question in the right place. I think that this particular question is on the border line between on-topic and off-topic. You should really consider asking your future questions somewhere else. | |
| Oct 2, 2011 at 22:24 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 94 characters in body
|
| Sep 30, 2011 at 23:51 | comment | added | Xavier Labouze | @Tayfun,about your comment :-) - What else do you think about the posted question ? | |
| Sep 30, 2011 at 21:33 | comment | added | Xavier Labouze | @Tsuyoshi : Tks for the link (naive questions do have virtues, I learnt this from my students). | |
| Sep 30, 2011 at 15:01 | comment | added | Tsuyoshi Ito | Well, if you think that your questions are too naive, I have to agree. Honestly speaking, I think that you should have asked your questions on math.stackexchange.com instead of cstheory.stackexchange.com. They are by no means research-level questions in complexity theory. | |
| Sep 30, 2011 at 14:25 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 116 characters in body
|
| Sep 30, 2011 at 13:55 | comment | added | Tsuyoshi Ito | Also, please make an effort to state your question precisely, and update the question so that people can understand your question without reading comments. | |
| Sep 30, 2011 at 13:51 | comment | added | Tsuyoshi Ito | If you do not know the relation between PP and counting the number of solutions, please check a textbook on complexity theory such as Papadimitriou. | |
| Sep 30, 2011 at 13:44 | comment | added | Xavier Labouze | @Tsuyoshi: 1- Why is it necessary to introduce probalistic TM even if $m$ is exponentially large in the input size ? 2- Let $m$ be small enough, the question of reducibility from "Exactly $m$ SAT" to US remains. | |
| Sep 30, 2011 at 13:25 | comment | added | Tsuyoshi Ito | What if m is exponentially large in the input size? I think that you are using the PP oracle twice. | |
| Sep 30, 2011 at 12:52 | comment | added | Xavier Labouze | @Tsuyoshi: It is the same kind of oracle calls for US and "Exactly $m$ models" : First NP call : Has the formula more or equal $m$ models ? Second co-NP call : Has the formula stricly less than $m+1$ models ? | |
| Sep 30, 2011 at 12:25 | comment | added | Tsuyoshi Ito | @Xavier: I cannot see how to solve “Exactly m SAT” by using the NP oracle twice. Care to elaborate? | |
| Sep 30, 2011 at 11:47 | comment | added | Kaveh | @Tsuyoshi, you are right, I misunderstood the question. | |
| Sep 30, 2011 at 0:27 | comment | added | Tsuyoshi Ito | @Kaveh: I realized that I cannot understand your reduction even for m=2. How can you use the oracle for Unique SAT to find a solution for a SAT instance with two answers? Are you using the randomized reduction by Valiant and Vazirani? | |
| Sep 29, 2011 at 23:56 | comment | added | Tsuyoshi Ito | @Kaveh: I do not think that your reduction works unless m is polynomially bounded in the input size. | |
| Sep 29, 2011 at 23:49 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 21 characters in body
|
| Sep 28, 2011 at 5:04 | comment | added | Suresh Venkat | (I should cut and paste this :)): answers, not comments... | |
| Sep 27, 2011 at 23:00 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 9 characters in body
|
| Sep 27, 2011 at 21:40 | comment | added | Xavier Labouze | @Kaveh, 1. I meant what if the machine gives a no answer to the Exactly $m$ SAT problem ? (we don't have access to the number of solutions, $m$ is given) 2. Nice ! | |
| Sep 27, 2011 at 21:05 | comment | added | Kaveh | 1. the machine will tell the number of solutions or that it has more than $m$ solutions. 2. you can add the negation of conjunction describing the solution. | |
| Sep 27, 2011 at 12:17 | comment | added | Xavier Labouze | @Kaveh ,Tks. 1- what if the initial formula hasn't exactly m models ? (possibly exactly one); 2- how to be sure that the added clause eliminates no more than one solution ? (then we would have to test the values of m'<m) | |
| Sep 27, 2011 at 6:06 | comment | added | Kaveh | It is polytime Turing reducible: find a solution, add a clause eliminating it, and repeat till the formula becomes unsatisfiable. | |
| Sep 27, 2011 at 1:01 | history | tweeted | twitter.com/#!/StackCSTheory/status/118490496963325952 | ||
| Sep 26, 2011 at 23:07 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 2 characters in body; edited title
|
| Sep 26, 2011 at 20:52 | history | asked | Xavier Labouze | CC BY-SA 3.0 |