# Tag Info

Accepted

### May Boolean circuits be exponentially more concise than Boolean formulae?

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound ...

• 14.9k

### XORSAT to HornSAT reduction

You can’t do this. By Schaefer's dichotomy theorem, satisfiability of sets of XOR clauses mixed with Horn clauses is an NP-complete problem, hence it does not have a poly-time reduction to Horn-SAT ...
• 14.9k