Timeline for Hardness of finding a true or a false assignment into a generic boolean formula?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Jan 23, 2013 at 5:20 | comment | added | Kaveh | We can always introduce new propositional variables to obtain an equivalent polysize CNF formula as is done in reduction from SAT to CNF-SAT, the blow up is only if we don't introduce new variables. | |
| Dec 8, 2012 at 23:08 | history | edited | Juho | CC BY-SA 3.0 |
added 210 characters in body
|
| Dec 5, 2012 at 20:29 | comment | added | Juho | @SAT No, unfortunately not. An exponential blowup of the formula is possible in some cases. | |
| Dec 5, 2012 at 19:37 | comment | added | SAT | but if i have a generic formula the operation of converting to SAT is polinomial in space and time? | |
| Dec 5, 2012 at 19:11 | history | answered | Juho | CC BY-SA 3.0 |