Expressing Linear Orders Requires Exponential-Size DNNFs
classification
💻 cs.CC
cs.AIcs.LO
keywords
linearorderscandidatesdnnfexpressingsizecircuitcircuits
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.