LSM is not generated by binary functions
classification
💻 cs.CC
keywords
functionsbinarydefinedanswerapproximatearxivaskedbulatov
read the original abstract
The material in this note is now superseded by arXiv:1108.5288v4. Bulatov et al. [1] defined the operation of (efficient) pps_\omega-definability in order to study the computational complexity of certain approximate counting problems. They asked whether all log-supermodular functions can be defined by binary implication and unary functions in this sense. We give a negative answer to this question.
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.