Complexity of satisfiability problems with symmetric polynomial clauses

DOI10.1093/LOGCOM/7.3.353zbMATH Open0879.68054OpenAlexW2076477022MaRDI QIDQ4344698FDOQ4344698

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

Recommendations

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

zbMATH Keywords

NP-complete problemsCNF-satisfiabilityproblem SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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
• Title not available (Why is that?)
• 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)