An initial study of time complexity in infinite-domain constraint satisfaction
type: Item
instance of: scholarly article
title: An initial study of time complexity in infinite-domain constraint satisfaction
zbMATH Open document ID: 1402.68162
author: Peter Jonsson
author: Victor Lagerkvist
published in: Artificial Intelligence
publication date: 2017-02-28T00:00:00Z
full work available at URL: http://urn.kb.se/resolve
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6689858
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: infinite domain
zbMATH Keywords: time complexity
MaRDI profile type: Publication
OpenAlex ID: W2582970508
cites work: On sunflowers and matrix multiplication
cites work: A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
cites work: The complexity of infinite \(H\)-colouring
cites work: Q3003675
cites work: Set Partitioning via Inclusion-Exclusion
cites work: Constraint Satisfaction Problems with Infinite Templates
cites work: Collapsibility in Infinite-Domain Quantified Constraint Satisfaction
cites work: Tractable Set Constraints
cites work: The Complexity of Phylogeny Constraint Satisfaction
cites work: The complexity of equality constraint languages
cites work: The complexity of temporal constraint satisfaction problems
cites work: The Complexity of Rooted Phylogeny Problems
cites work: Point algebras for temporal reasoning: Algorithms and complexity
cites work: Disjunctions, independence, refinements
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Strong computational lower bounds via parameterized complexity
cites work: An Isomorphism Between Subexponential and Parameterized Complexity Theory
cites work: Building tractable disjunctive constraints
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: Reasoning about partially ordered events
cites work: Reasoning about action in polynomial time
cites work: Q4733384
cites work: Parametrized complexity theory.
cites work: Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
cites work: Expressive power and complexity in algebraic logic
cites work: A finite relation algebra with undecidable network satisfaction problem
cites work: Q4336034
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: A unifying approach to temporal constraint reasoning
cites work: Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
cites work: Q4255576
cites work: Reasoning about temporal relations
cites work: Q3010376
cites work: Q4475644
cites work: A full derandomization of schöning's k-SAT algorithm
cites work: The number of trees
cites work: Counting unlabeled structures
cites work: Q4533361
cites work: Q3184605
cites work: On the Limits of Sparsification
cites work: A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
cites work: Backtracking algorithms for disjunctions of temporal constraints
cites work: An optimal algorithm for generating equivalence relations on a linear array of processors
cites work: The Time Complexity of Constraint Satisfaction
cites work: Q5750422
cites work: Algorithms for Sat and upper bounds on their complexity
cites work: Q4414647
cites work: Constant Time Generation of Free Trees
DOI: 10.1016/J.ARTINT.2017.01.005
description: scientific article; zbMATH DE number 6689858