Timeline for The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2023 at 9:37 | comment | added | Jukka Kohonen | Your equivalence seems very mild. For example, same collection of clauses in different order = different formula? In a clause, same literals in different order = different clause? So in essence, from all $(2n)^3$ possible clauses, take any subset of any size in any order? | |
| Feb 9, 2023 at 5:23 | history | edited | Tony Huynh |
edited tags
|
|
| Aug 21, 2022 at 11:32 | vote | accept | user1642683 | ||
| Aug 20, 2022 at 18:23 | comment | added | LSpice | Name of @JimConant's reference: Conant and Thistlethwaite - Boolean formulae, hypergraphs and combinatorial topology. | |
| Aug 20, 2022 at 18:22 | history | edited | LSpice | CC BY-SA 4.0 |
Capitalise title
|
| Aug 20, 2022 at 18:09 | answer | added | Tony Huynh | timeline score: 5 | |
| Aug 20, 2022 at 17:53 | comment | added | Jim Conant | Marginally related: in arxiv.org/pdf/0808.0739.pdf, we showed that the set of satisfiable formula in $\ell$-CNF in $n$ variables is homotopy equivalent to the Alexander dual of the hypergraph of $\ell$-faces of the $n$-cube. | |
| Aug 20, 2022 at 17:31 | history | edited | Alexander Pruss | CC BY-SA 4.0 |
fixed spelling, punctuation and phrasing
|
| Aug 20, 2022 at 15:15 | history | edited | YCor | CC BY-SA 4.0 |
formatting
|
| Aug 20, 2022 at 11:47 | history | edited | user1642683 | CC BY-SA 4.0 |
added 95 characters in body
|
| S Aug 20, 2022 at 11:45 | review | First questions | |||
| Aug 20, 2022 at 17:32 | |||||
| S Aug 20, 2022 at 11:45 | history | asked | user1642683 | CC BY-SA 4.0 |