Is the set of satisfiable Horn formulas sparse?

A sparse language contains a polynomially bounded number of srings at every length.


No. Fix a $k$, and let $x_1, x_2, ..., x_k$ be the variables in your Horn formula. Then for all $i$ the clause $(x_i)$ is a Horn clause – there is at most one positive literal. Using such clauses, you can construct $2^k - 1$ different Horn formulas: $(x_1)$; $(x_2)$; $(x_1) \wedge (x_2)$; $(x_3)$; etc. Each of these is trivially satisfiable – just set $x_i = 1$ for all $i$. The length of each formula is $O(k \log k)$, assuming any reasonable encoding.

(You can add extra requirements like "all clauses must contain at least one negative literal", "all variables must occur in at least one clause", etc., but this doesn't really change anything; just tweak the above construction slightly.)

  • $\begingroup$ using your construction, Is the set of unsatisfiable Horn formulas dense? $\endgroup$ – Mohammad Al-Turkistany Aug 26 '10 at 18:39
  • 1
    $\begingroup$ Should be: To make any Horn formula unsatisfiable, make sure it contains $x_i \wedge \neg x_i$ --- and you can add this to every formula above. $\endgroup$ – Evgenij Thorstensen Aug 26 '10 at 20:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.