Timeline for SAT and Arithmetic Geometry
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2012 at 11:35 | comment | added | Emil Jeřábek | @Will: If you encode 3SAT instead of SAT, each clause will have a constant-size translation, no matter how complex the translation of $\lor$ is. | |
| Dec 7, 2012 at 17:40 | comment | added | Will Sawin | Silly notational point: If you literally use $x+y-xy$, your formula could get exponentially long. One could solve this by introducing new variables but I think it's more elegant to just write $1-(1-x)(1-y)$. | |
| Dec 6, 2012 at 16:19 | history | answered | Benjamin Steinberg | CC BY-SA 3.0 |