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

NP-complete problemsCNF-satisfiabilityproblem 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

(8)

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

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)