New answers tagged

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 ...
notautogenerated's user avatar
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 ...
a3nm's user avatar
  • 8,856

Top 50 recent answers are included