scientific article; zbMATH DE number 1775445

MaRDI QIDQ4542577zbMATH OpenFDO

Authors Michael Freedman

Publication date 1 August 2002

zbMATH Keywords

general Boolean formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of satisfiability problems
• A simplified NP-complete satisfiability problem
• On the complexity of k-SAT
• scientific article; zbMATH DE number 152108
• NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )

Cited in

(5)

• Determining the <I>SHOIN(D)</I>-Satisfiability with a Complete Disjunctive Normal Form Group
• Contributions to the domino problem: seeding, recurrence and satisfiability
• Boolean formulae, hypergraphs and combinatorial topology
• Karp's NP-complete problems over first-order definable structures
• Periodic constraint satisfaction problems: Tractable subclasses

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542577)