scientific article

zbMath0476.03020MaRDI QIDQ3931248

Evgeny Dantsin

Publication date: 1981

Full work available at URL: https://eudml.org/doc/68840

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

propositional tautologiesclasses with polynomial time recognition algorithm

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Complexity of proofs (03F20)

Related Items

A randomized algorithm for 3-SAT ⋮ Worst-case study of local search for MAX-\(k\)-SAT. ⋮ On the complexity of unique circuit SAT ⋮ UnitWalk: A new SAT solver that uses local search guided by unit clause elimination ⋮ MAX SAT approximation beyond the limits of polynomial-time approximation