Expressing Linear Orders Requires Exponential-Size DNNFs

07/17/2018
by   Ronald de Haan, et al.
0

We show that any DNNF circuit that expresses the set of linear orders over a set of n candidates must be of size 2^Ω(n).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset