5
$\begingroup$

Let's suppose we have propositional variables $x_1 ... x_n$. A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$. So, there are $2^n$ possible valuations. The number of sets of valuations is then $2^{2^n}$. If we associate to each formula $\varphi$ the set of valuations that satisfy it, we see that there are many sets of valuations that do not correspond to any 3CNF formula. This is because there are only polynomially many possible 3CNF clauses and any formula is a subset of such clauses.

Is there any theory about the structure of the sets of valuations representable by 3CNF formulas?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ A trivial note: given a 3-CNF, determining the size of such set (i.e. the number of satisfying assignments) is #P-complete. $\endgroup$ – Vor Jan 29 '16 at 17:18
  • $\begingroup$ May be you are referring to 3CNF's with poly($n$) clauses? $\endgroup$ – Karthik C. S. Jan 29 '16 at 20:04
  • $\begingroup$ Every 3CNF formula with n variables has poly(n) clauses: 3 literals per clause, so 2n choices for the first literal, 2n for the second, 2n for the third gives you 8n^3 as a crude upper bound for the number of clauses $\endgroup$ – Brian Jan 30 '16 at 9:34
  • $\begingroup$ A lot is known about random 3CNFs, but these are only properties that hold with high probability. Other than that, an excellent description of the sets of valuations is that they arise from 3CNFs. What more would you want? $\endgroup$ – Yuval Filmus Jan 31 '16 at 10:04
  • $\begingroup$ I'd be interested in the combinatorics, first of all. Fix n variables, let k <= 2^n, what can we say about valuation sets of size k that correspond to some formula phi. Do such sets exist for every k, for example? Perhaps we can define an equivalence relation, say, by permuting the variables and then look at the equivalence classes. How many classes are there, what can we say about them, etc. Maybe not that exactly, but something like that. $\endgroup$ – Brian Jan 31 '16 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.