Can I read Expressing Linear Orders Requires Exponential-Size DNNFs on EtoBox?

Expressing Linear Orders Requires Exponential-Size DNNFs by de Haan, Ronald is a scholarly article available to read on EtoBox.

What is Expressing Linear Orders Requires Exponential-Size DNNFs about?

We show that any DNNF circuit that expresses the set of linear orders over a set of $n$ candidates must be of size $2^{\Omega(n)}$. Moreover, we show that there exist DNNF circuits of size $2^{O(n)}$ expressing linear orders over $n$ candidates.

Author

de Haan, Ronald

Published

2018

Language

EN