On k-positive satisfiability problem

DOI10.1007/BF02948732MaRDI QIDQ1964360zbMATHOpenAlexFDO

Authors Xiong Huang, Wei Li

Publication date 1999

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02948732

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Solving satisfiability in less than \(2^ n\) steps
• scientific article; zbMATH DE number 515744
• A hierarchy of tractable satisfiability problems
• Algorithms – ESA 2005
• Polynomially solvable satisfiability problems

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 515744 (Why is no real title available?)
• A hierarchy of tractable satisfiability problems
• A linear algorithm for renaming a set of clauses as a Horn set
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Number of models and satisfiability of sets of clauses
• On the Complexity of Timetable and Multicommodity Flow Problems
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of theorem-proving procedures
• Unit Refutations and Horn Sets

Cited in

(9)

• scientific article; zbMATH DE number 4106815 (Why is no real title available?)
• An algorithm based on tabu search for satisfiability problem
• On the K‐sat model with large number of clauses
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• A hierarchy of tractable satisfiability problems
• A Note on a Problem Posed by D. E. Knuth on a Satisfiability Recurrence
• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• Solving satisfiability in less than \(2^ n\) steps

This page was built for publication: On \(k\)-positive satisfiability problem

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