Constructing NP-intermediate problems by blowing holes with parameters of various properties

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

zbMATH Keywords

computational complexityconstraint satisfaction problemsNP-intermediate problemsabduction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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