An initial study of time complexity in infinite-domain constraint satisfaction

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Which problems have strongly exponential complexity?
Parametrized complexity theory.
The complexity of temporal constraint satisfaction problems
On the complexity of \(k\)-SAT
A unifying approach to temporal constraint reasoning
Building tractable disjunctive constraints
Reasoning about temporal relations
Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
The complexity of equality constraint languages
Algorithms for Sat and upper bounds on their complexity
The number of trees
The Time Complexity of Constraint Satisfaction
Set Partitioning via Inclusion-Exclusion
Strong computational lower bounds via parameterized complexity
A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
Disjunctions, independence, refinements
The complexity of infinite \(H\)-colouring
On the Limits of Sparsification
A full derandomization of schöning's k-SAT algorithm
Tight lower bounds for certain parameterized NP-hard problems
On sunflowers and matrix multiplication
A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
The Complexity of Rooted Phylogeny Problems
Constant Time Generation of Free Trees
An Isomorphism Between Subexponential and Parameterized Complexity Theory
A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
A finite relation algebra with undecidable network satisfaction problem
Point algebras for temporal reasoning: Algorithms and complexity
Counting unlabeled structures
Reasoning about partially ordered events
Backtracking algorithms for disjunctions of temporal constraints
Reasoning about action in polynomial time
Collapsibility in Infinite-Domain Quantified Constraint Satisfaction
Expressive power and complexity in algebraic logic
The Complexity of Phylogeny Constraint Satisfaction
Tractable Set Constraints
Constraint Satisfaction Problems with Infinite Templates
Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
An optimal algorithm for generating equivalence relations on a linear array of processors

Cited In (7)

Title not available (Why is that?)
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Title not available (Why is that?)
Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
On prime scenarios in qualitative spatial and temporal reasoning
Title not available (Why is that?)
General lower bounds and improved algorithms for infinite-domain CSPs

This page was built for publication: An initial study of time complexity in infinite-domain constraint satisfaction

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