An algorithm for the satisfiability problem of formulas in conjunctive normal form

DOI10.1016/j.jalgor.2004.04.012zbMath1090.68052OpenAlexW2067983896MaRDI QIDQ4651809

Rainer Schuler

Publication date: 22 February 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.04.012

zbMATH Keywords

NP-completenessComplexity theoryProbabilistic algorithmsCNF-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (21)

An improved upper bound for SAT ⋮ A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Towards NP-P via proof complexity and search ⋮ Analysis of local search landscapes for \(k\)-SAT instances ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ On the exact complexity of evaluating quantified \(k\)-\textsc{cnf} ⋮ Satisfiability Certificates Verifiable in Subexponential Time ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ On the Exact Complexity of Evaluating Quantified k-CNF ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ The Complexity of Satisfiability of Small Depth Circuits ⋮ CNF satisfiability in a subspace and related problems ⋮ Unnamed Item ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

This page was built for publication: An algorithm for the satisfiability problem of formulas in conjunctive normal form