Constructing NP-intermediate problems by blowing holes with parameters of various properties
From MaRDI portal
Publication:2345449
DOI10.1016/j.tcs.2015.03.009zbMath1318.68094OpenAlexW2046420210MaRDI QIDQ2345449
Peter Jonsson, Gustav Nordh, Victor Lagerkvist
Publication date: 22 May 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.009
Related Items
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, A Dichotomy Theorem for the Inverse Satisfiability Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Computational complexity of linear constraints over the integers
- The complexity of unions of disjoint sets
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- The complexity of propositional closed world reasoning and circumscription
- Semantics and complexity of abduction from default theories
- Which problems have strongly exponential complexity?
- What makes propositional abduction tractable
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Approximating fractional hypertree width
- Sublattices of the polynomial time degrees
- Non-dichotomies in Constraint Satisfaction Complexity
- Understanding the Complexity of Induced Subgraph Isomorphisms
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Linear FPT reductions and computational lower bounds
- Constraint solving via fractional edge covers
- Complexity of Finding Embeddings in a k-Tree
- Natural Self-Reducible Sets
- On the complexity of integer programming
- On the Structure of Polynomial Time Reducibility
- `` Strong NP-Completeness Results
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of logic-based abduction
- Closure properties of constraints
- Reducibility among Combinatorial Problems
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- On the complexity of \(k\)-SAT
