<p>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.</p>

<p>(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.)</p>

CC BY-SA 2.5
2010-08-26T18:39:31.103Z
using your construction, Is the set of unsatisfiable Horn formulas dense?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-08-26T20:55:22.140Z
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.
Evgenij Thorstensen
CC BY-SA 2.5
2010-08-26T18:27:58.603Z
2010-08-26T18:39:31.960Z
2010-08-26T18:39:31.960Z
Jukka Suomela
<p>Is the set of satisfiable Horn formulas sparse?</p>

<p>A sparse language contains a polynomially bounded number of srings at every length.</p>

<cc.complexity-theory><complexity-classes><np>
Sparsity of Horn satisfiability?
Mohammad Al-Turkistany
# Sparsity of Horn satisfiability?

(Asked by: username_0 on 2010-08-26)

Is the set of satisfiable Horn formulas sparse?

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

**Tags:** cc.complexity-theory, complexity-classes, np

---

## 1 answers

### Answer by username_1 on 2010-08-26. Score: 6 | Accepted answer

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.)

> **Comments:**
> **username_0**: using your construction, Is the set of unsatisfiable Horn formulas dense?  
> **username_2**: 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.  

---

