New Algorithms for #2-SAT and #3-SAT
Authors: Junqiang Peng, Zimo Sheng, Mingyu Xiao
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose two novel algorithms, Alg2CNF and Alg3CNF, for weighted #2-SAT and weighted #3-SAT, achieving runtime bounds of O (1.1082m) and O (1.4423m), respectively. The algorithms and complexity bounds directly apply to the unweighted case, significantly improving upon previous results. To this end, we bring new techniques for (weighted) #2-SAT and #3-SAT. |
| Researcher Affiliation | Academia | 1University of Electronic Science and Technology of China, Chengdu, China 2Anhui University |
| Pseudocode | Yes | Algorithm 1 Alg2CNF(F, w, W) and Algorithm 2 Alg3CNF(F, w, W) |
| Open Source Code | No | The paper does not provide an explicit statement or a link to source code for the algorithms described. It mentions "https://mccompetition.org/" in a footnote, but this refers to the annual Model Counting Competition and not the authors' own implementation code. |
| Open Datasets | No | The paper focuses on theoretical algorithm design and complexity analysis for #2-SAT and #3-SAT problems. It does not describe or use any specific datasets for empirical evaluation, hence no information regarding publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Consequently, there is no mention of dataset splits (training, validation, test) required for reproducibility. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design and complexity analysis. There is no mention of any specific hardware (e.g., CPU, GPU models, memory) used for running experiments. |
| Software Dependencies | No | The paper is theoretical, focusing on algorithmic design and complexity. It does not provide specific software dependencies or version numbers for any implementation details that would be required to reproduce experimental results. |
| Experiment Setup | No | The paper focuses on the theoretical analysis and design of algorithms for #2-SAT and #3-SAT. It does not describe any specific experimental setup, hyperparameters, or training configurations, as it does not involve empirical experiments. |