2022/12/06 by Guillaume Escamocher, Escamocher, Guillaume, Barry O’Sullivan +1
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Management and Algorithms #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2212.02893
openalex publication_date 2022/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a way to create small yet difficult model counting instances. Our generator is highly parameterizable: the number of variables of the instances it produces, as well as their number of clauses and the number of literals in each clause, can all be set to any value. Our instances have been tested on state of the art model counters, against other difficult model counting instances, in the Model Counting Competition. The smallest unsolved instances of the competition, both in terms of number of variables and number of clauses, were ours. We also observe a peak of difficulty when fixing the number of variables and varying the number of clauses, in both random instances and instances built by our generator. Using these results, we predict the parameter values for which the hardest to count instances will occur.