Complexity of satisfiability problems with symmetric polynomial clauses

DOI10.1093/LOGCOM/7.3.353MaRDI QIDQ4344698zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Malika More

Publication date 12 January 1998

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/7.3.353

zbMATH Keywords

CNF-satisfiabilityNP-complete problemsproblem SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of generalized satisfiability counting problems
• The complexity of satisfiability problems
• The complexity of minimal satisfiability problems
• A simplified NP-complete satisfiability problem

Cited in

(9)

• Polynomial-average-time satisfiability problems
• A perspective on certain polynomial-time solvable classes of satisfiability
• Complexity of generalized satisfiability counting problems
• Recognition of tractable satisfiability problems through balanced polynomial representations
• scientific article; zbMATH DE number 2127871 (Why is no real title available?)
• About some UP-based polynomial fragments of SAT
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Complexity of the satisfiability problem for multilinear forms over a finite field

This page was built for publication: Complexity of satisfiability problems with symmetric polynomial clauses

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