Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Capitalise title
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69

the The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically the same modulo repeated clauses. Thus $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee x_1\vee \neg x_1)$$$$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor x_1\lor \lnot x_1)$$ are the same while $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee \neg x_1\vee x_1)$$$$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor \lnot x_1\lor x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones? If the exact numbers cannot be given, just some recurrence formulas will do. Does the $\operatorname{lim}$$\lim$ of the fraction of satisfiable ones go to $0$ as $n\to \infty$?

the number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically the same modulo repeated clauses. Thus $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee x_1\vee \neg x_1)$$ are the same while $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee \neg x_1\vee x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones? If the exact numbers cannot be given, just some recurrence formulas will do. Does the $\operatorname{lim}$ of the fraction of satisfiable ones go to $0$ as $n\to \infty$?

The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically the same modulo repeated clauses. Thus $$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor x_1\lor \lnot x_1)$$ are the same while $$(x_1\lor x_1\lor \lnot x_1)\text{ and } (x_1\lor x_1\lor \lnot x_1)\land (x_1\lor \lnot x_1\lor x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones? If the exact numbers cannot be given, just some recurrence formulas will do. Does the $\lim$ of the fraction of satisfiable ones go to $0$ as $n\to \infty$?

fixed spelling, punctuation and phrasing
Source Link

What is the number of $3$-CNF (closedconjunctive normal form) formulas inwith $n$-variables sentential variables and what is the fraction of satisfiable ones  ? I consider 2 forumlastwo formulas the same if they are syntactically the same and do not containmodulo repeated clauses. Thus $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee x_1\vee \neg x_1)$$ are the same while $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee \neg x_1\vee x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones  ? If the exact numbers cannot be given, just some recurrence formulas will do.Does Does the $\operatorname{lim}$ of the fraction of satisfiable ones go to $0$ ansas $n\to \infty$  ?

What is the number of $3$-CNF (closed normal form) formulas in $n$-variables and what is the fraction of satisfiable ones  ? I consider 2 forumlas the same if they are syntactically the same and do not contain repeated clauses. Thus $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee x_1\vee \neg x_1)$$ are the same while $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee \neg x_1\vee x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones  ? If the exact numbers cannot be given, just some recurrence formulas will do.Does the $\operatorname{lim}$ of the fraction of satisfiable ones go to $0$ ans $n\to \infty$  ?

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically the same modulo repeated clauses. Thus $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee x_1\vee \neg x_1)$$ are the same while $$(x_1\vee x_1\vee \neg x_1)\text{ and } (x_1\vee x_1\vee \neg x_1)\wedge (x_1\vee \neg x_1\vee x_1)$$ are not. Now, what is the number of these equivalence classes of formulas in $n$ variables and what is the fraction of satisfiable ones? If the exact numbers cannot be given, just some recurrence formulas will do. Does the $\operatorname{lim}$ of the fraction of satisfiable ones go to $0$ as $n\to \infty$?

formatting
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Loading
added 95 characters in body
Source Link
Loading
Source Link
Loading