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 ...
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 ...
Top 50 recent answers are included
Related Tags
sat × 326cc.complexity-theory × 148
ds.algorithms × 43
np-hardness × 38
reference-request × 34
counting-complexity × 29
lo.logic × 25
complexity-classes × 21
reductions × 21
graph-theory × 16
time-complexity × 13
proof-complexity × 13
boolean-functions × 12
lower-bounds × 11
polynomial-time × 11
random-k-sat × 11
approximation-hardness × 10
upper-bounds × 9
boolean-formulas × 9
approximation-algorithms × 8
circuit-complexity × 8
np-complete × 8
np × 8
csp × 8
phase-transition × 8