The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness

DOI10.1016/0304-3975(94)00182-IMaRDI QIDQ673091zbMATHFDO

Authors Nadia Creignou

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

satisfiability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 515731
• The complexity of satisfiability problems
• A simplified NP-complete satisfiability problem
• scientific article; zbMATH DE number 515738

Cites work

• scientific article; zbMATH DE number 4101157 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3551893 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512986 (Why is no real title available?)
• scientific article; zbMATH DE number 515738 (Why is no real title available?)
• A remark on a problem of Harary
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Linear time transformations between combinatorial problems
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• On the completeness of a generalized matching problem
• Optimization, approximation, and complexity classes
• Power indices and easier hard problems
• Satisfiability Is Quasilinear Complete in NQL
• Sorting, linear time and the satisfiability problem
• The complexity of satisfiability problems

Cited in

(14)

• Exact complexity of problems of incompletely specified automata
• Finding kernels or solving SAT
• A multivariate approach for checking resiliency in access control
• Expressive power of digraph solvability
• Kernels in digraphs that are not kernel perfect
• Some observations on holographic algorithms
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• The cardinality constrained covering traveling salesman problem
• An alternative approach for proving the NP-hardness of optimization problems
• scientific article; zbMATH DE number 515731 (Why is no real title available?)
• On unique graph 3-colorability and parsimonious reductions in the plane
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• Propositional discourse logic
• Argumentation frameworks as constraint satisfaction problems

This page was built for publication: The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness

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