A threshold for a polynomial solution of \#2SAT

MaRDI QIDQ2892663zbMATH OpenFDO

Authors Guillermo De Ita, J. Raymundo Marcial-Romero, José Hernández

Publication date 19 June 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL http://iospress.metapress.com/content/136706724808641n/fulltext.html

zbMATH Keywords

\#2SAT problembranch-bound algorithmefficient countingpolynomial thresholds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• Polynomially solvable satisfiability problems
• On quadratic threshold CSPs
• On quadratic threshold CSPs
• Upper bounds on the satisfiability threshold
• The asymptotic \(k\)-SAT threshold
• The asymptotic k-SAT threshold
• Satisfiability and derandomization for small polynomial threshold circuits
• The satisfiability threshold for k-XORSAT
• On Threshold Circuits and Polynomial Computation

Cited in

(4)

• Using binary patterns for counting falsifying assignments of conjunctive forms
• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• A bottom-up algorithm for solving \#2SAT
• Tensor network contractions for \#SAT

This page was built for publication: A threshold for a polynomial solution of \#2SAT

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