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

DOI10.1016/J.ARTINT.2017.01.005MaRDI QIDQ514144zbMATH OpenOpenAlexFDO

Authors Peter Jonsson, Victor Lagerkvist

Publication date 28 February 2017

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-136570

zbMATH Keywords

constraint satisfactiontime complexityinfinite domain

Mathematics Subject Classification ID

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

Recommendations

• Fine-grained time complexity of constraint satisfaction problems
• Time complexity of constraint satisfaction via universal algebra
• The Time Complexity of Constraint Satisfaction
• The complexity of constraint satisfaction problems (invited talk)
• The complexity of temporal constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 5916930 (Why is no real title available?)
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 2084717 (Why is no real title available?)
• scientific article; zbMATH DE number 1753151 (Why is no real title available?)
• scientific article; zbMATH DE number 4119600 (Why is no real title available?)
• scientific article; zbMATH DE number 4185056 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A finite relation algebra with undecidable network satisfaction problem
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
• A unifying approach to temporal constraint reasoning
• Algorithms for Sat and upper bounds on their complexity
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• An optimal algorithm for generating equivalence relations on a linear array of processors
• Backtracking algorithms for disjunctions of temporal constraints
• Building tractable disjunctive constraints
• Collapsibility in Infinite-Domain Quantified Constraint Satisfaction
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Constant Time Generation of Free Trees
• Constraint Satisfaction Problems with Infinite Templates
• Counting unlabeled structures
• Disjunctions, independence, refinements
• Expressive power and complexity in algebraic logic
• Handbook of constraint programming.
• Improved bounds on Bell numbers and on moments of sums of random variables
• On sunflowers and matrix multiplication
• On the complexity of \(k\)-SAT
• On the limits of sparsification
• Parametrized complexity theory.
• Point algebras for temporal reasoning: Algorithms and complexity
• Reasoning about action in polynomial time
• Reasoning about partially ordered events
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Set partitioning via inclusion-exclusion
• Strong computational lower bounds via parameterized complexity
• The Complexity of Rooted Phylogeny Problems
• The Time Complexity of Constraint Satisfaction
• The complexity of equality constraint languages
• The complexity of infinite \(H\)-colouring
• The complexity of phylogeny constraint satisfaction
• The complexity of temporal constraint satisfaction problems
• The number of trees
• Tight lower bounds for certain parameterized NP-hard problems
• Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
• Tractable set constraints
• Which problems have strongly exponential complexity?

Cited in

(9)

• Computational Short Cuts in Infinite Domain Constraint Satisfaction
• The Time Complexity of Constraint Satisfaction
• On prime scenarios in qualitative spatial and temporal reasoning
• Recent Advances in Constraints
• Deciding the consistency of branching time interval networks
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• General lower bounds and improved algorithms for infinite-domain CSPs
• Why are CSPs based on partition schemes computationally hard?
• scientific article; zbMATH DE number 7760475 (Why is no real title available?)

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)