0
$\begingroup$

given some $n$ variables I would be interested to know what is the count of all 3SAT formulas under $n$ that are unsatisfiable.

An example of all 3SAT forumlas under $n=3$ is the following: $$ ( x \lor y \lor z) = Satisfiable \\ ... \\ ( x \lor y \lor z)\land ( \neg x \lor \neg y \lor z)= Satisfiable \\ ... \\ ( x \lor y \lor z)\land( x \lor y \lor \neg z).....( \neg x \lor \neg y \lor \neg z) = Unsatisfiable $$ The total count of $n=3$ would be 1, because only the last formula is actually unsatisfiable

as you can see, even with a small number such as $n=3$ there are 256 different formulas, going even a single digit up to $n=4$ will result in $2^{32}$ different formulas, so it cannot be simulated.

Therefor I was wondering, is there any way of knowing just the count without having to check it one by one?

Improve this question
$\endgroup$
5
  • $\begingroup$ are you interested in exact answers, or approximate is sufficient? $\endgroup$
    – Ameer Jewdaki
    Jul 8, 2022 at 23:11
  • 1
    $\begingroup$ There are some interesting asymptotic bounds: If you draw a 3SAT formula randomly with $n$ variables and $m$ clauses, almost all with $\frac{m}{n}> 4.267$ are unsatisfiable, and almost all with $ \frac{m}{n}<4.267$ are satisfiable. You can easily calculate the number of these. See cs.stackexchange.com/a/86544/44709 $\endgroup$
    – Ameer Jewdaki
    Jul 9, 2022 at 15:43
  • $\begingroup$ What does it mean for a formula to be "under $n$"? $\endgroup$
    – D.W. ♦
    Jul 9, 2022 at 18:28
  • $\begingroup$ Have you checked oeis.org? $\endgroup$
    – D.W. ♦
    Jul 9, 2022 at 18:28
  • $\begingroup$ @AmeerJewdaki although not exactly answering it does provide interesting and valuable insight, thank you $\endgroup$
    – matan Pleblist
    Jul 9, 2022 at 19:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.