A lower bound on CNF encodings of the at-most-one constraint
Authors:
- Petr KučeraPKPetr Kučera
- Petr SavickýPSPetr Savický
- Vojtěch VorelVVVojtěch Vorel
- 1 March 2019
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 762, 51-73
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Grantová Agentura České Republiky (GA15-15511S)
- Grantová Agentura České Republiky (GBP202/12/G061)
This publication has 5 references indexed in Scilit:
- Complexity issues related to propagation completenessArtificial Intelligence, 2013
- Boolean Functions2011
- Cardinality Networks: a theoretical and empirical studyConstraints, 2011
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960