Timeline for Worst simultaneous blowup when converting to CNF and DNF
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22, 2020 at 3:49 | vote | accept | salvalcantara | ||
| May 22, 2020 at 3:14 | comment | added | salvalcantara | Expanding a bit on the size, one could also consider the size of a formula to be the number of operators (and, or, not) on it, since that corresponds to the required number of logical gates in a hardware implementation. | |
| May 22, 2020 at 2:49 | comment | added | salvalcantara | I guess size would correspond to the number of "groups" (clauses or terms). Another option would be to count the total number of literals. Yet another option, these two options could be combined, and define size as the average size of "groups" (clauses or terms), where the size of a group would be the number of literals on it. Whatever measure captures the complexity of a formula in a better way, I am not sure what that measure is, so I left it open in my question. | |
| May 21, 2020 at 20:35 | answer | added | Yuval Filmus | timeline score: 0 | |
| May 21, 2020 at 20:28 | comment | added | Yuval Filmus | How do you measure the size of a CNF/DNF? | |
| May 21, 2020 at 19:34 | history | edited | salvalcantara | CC BY-SA 4.0 |
edited body
|
| May 21, 2020 at 19:33 | comment | added | salvalcantara | Sure, a formula halfway between CNF and DNF will blow up both ways, but I would like to characterize the worst case more precisely. | |
| May 21, 2020 at 18:17 | comment | added | Shaull | Do you want to know how to compute this bound, or how big it can get in general? For the latter, you can just take a formula that is partially in CNF and partially in DNF, so it blows up both ways. | |
| May 21, 2020 at 17:40 | review | First posts | |||
| May 21, 2020 at 20:22 | |||||
| May 21, 2020 at 17:39 | history | asked | salvalcantara | CC BY-SA 4.0 |