New answers tagged sat
2
votes
Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas
Partially answering question (2), the Prover-Delayer game of Atserias and Dalmau can be interpreted as a more general "dag-like query complexity" specialized to CNFs. See e.g. GGKS'18. And ...
- 216
13
votes
Accepted
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Somewhat surprisingly to me, this problem is in fact in PTIME.
The key insight is that, considering a clause $C$, letting $0 \leq k \leq 3$ be the number of negated literals in $C$, then the clause is ...
- 8,856
Top 50 recent answers are included