Timeline for Can a propositional threshold connective be expressed by standard connectives?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Feb 6, 2015 at 23:27 | review | Close votes | |||
| Feb 12, 2015 at 2:56 | |||||
| Feb 6, 2015 at 23:08 | comment | added | D.W.♦ | possible duplicate of Encoding 1-out-of-n constraint for SAT solvers | |
| Feb 6, 2015 at 13:41 | history | tweeted | twitter.com/#!/StackCompSci/status/563694040282300416 | ||
| Feb 6, 2015 at 0:40 | vote | accept | user109711 | ||
| Feb 6, 2015 at 0:11 | answer | added | Yuval Filmus | timeline score: 4 | |
| Feb 5, 2015 at 17:57 | history | edited | user109711 | CC BY-SA 3.0 |
added 1190 characters in body
|
| Feb 5, 2015 at 17:35 | comment | added | Raphael | Please edit your question to include your attempts and information you got. | |
| Feb 5, 2015 at 16:47 | comment | added | user109711 | The initial question is here: cstheory.stackexchange.com/questions/29389/… but I cannot understand the explanation. What about the specific case when n=5 and k=2 as above, for instance? | |
| Feb 5, 2015 at 16:29 | comment | added | user109711 | Intuitively, I would express it as an exponential sized DNF formula containing $\binom{n}{k}$ conjonctions of literals. For instance, for $n=5$ and $k=2$, the corresponding formula would be $(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_4) \vee (\neg x_1 \wedge \neg x_2 \wedge \neg x_5) \vee (\neg x_2 \wedge \neg x_3 \wedge \neg x_4) \vee \dots$ I do not see a more succinct way to do it. I have asked the question on cstheory.stackexchange.com, but the question seems not appropriate there. The answer may be obvious, but not to me... | |
| Feb 5, 2015 at 16:08 | history | edited | Raphael |
edited tags
|
|
| Feb 5, 2015 at 15:58 | review | First posts | |||
| Feb 5, 2015 at 20:04 | |||||
| Feb 5, 2015 at 15:56 | history | asked | user109711 | CC BY-SA 3.0 |