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

DOI10.1016/0304-3975(94)00182-IzbMATH Open0874.68127MaRDI QIDQ673091FDOQ673091

Authors: Nadia Creignou 

Publication date: 28 February 1997

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

Recommendations

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

zbMATH Keywords

satisfiability

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• On unique graph 3-colorability and parsimonious reductions in the plane
• Expressive power of digraph solvability
• The cardinality constrained covering traveling salesman problem
• Finding kernels or solving SAT
• Kernels in digraphs that are not kernel perfect
• A Multivariate Approach for Checking Resiliency in Access Control
• Exact complexity of problems of incompletely specified automata
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• Title not available (Why is that?)
• An alternative approach for proving the NP-hardness of optimization problems
• Some observations on holographic algorithms
• Propositional discourse logic
• Reducing the generalised Sudoku problem to the Hamiltonian cycle problem
• 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)