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

DOI10.1016/0304-3975(94)00182-IzbMath0874.68127MaRDI QIDQ673091

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)

Related Items

An alternative approach for proving the NP-hardness of optimization problems ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ Expressive power of digraph solvability ⋮ Finding kernels or solving SAT ⋮ Kernels in digraphs that are not kernel perfect ⋮ Propositional discourse logic ⋮ Reducing the generalised Sudoku problem to the Hamiltonian cycle problem ⋮ Argumentation frameworks as constraint satisfaction problems ⋮ Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview ⋮ Exact complexity of problems of incompletely specified automata ⋮ A Multivariate Approach for Checking Resiliency in Access Control ⋮ The cardinality constrained covering traveling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Optimization, approximation, and complexity classes
• Sorting, linear time and the satisfiability problem
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• Linear time transformations between combinatorial problems
• Satisfiability Is Quasilinear Complete in NQL
• The complexity of satisfiability problems
• On the completeness of a generalized matching problem
• A remark on a problem of Harary
• Power indices and easier hard problems