New upper bound for the \#3-SAT problem

DOI10.1016/j.ipl.2007.06.017zbMath1184.68473OpenAlexW2042764910MaRDI QIDQ2380029

Konstantin Kutzkov

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.06.017

zbMATH Keywords

analysis of algorithmssatisfiabilitycounting solutions

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Counting Maximal Independent Sets in Subcubic Graphs ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected ⋮ Solving and sampling with many solutions ⋮ Counting Independent Sets in Claw-Free Graphs

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• Number of models and satisfiability of sets of clauses
• Counting models for 2SAT and 3SAT formulae
• New methods for 3-SAT decision and worst-case analysis
• Counting the number of solutions for instances of satisfiability
• The Complexity of Enumeration and Reliability Problems
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: New upper bound for the \#3-SAT problem