Classifying the complexity of constraints using finite algebras

Classifying the complexity of constraints using finite algebras

Taispeáin leaganacha eile (1)

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Bulatov, A, Jeavons, P, Krokhin, A
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	2005

Míreanna comhchosúla

Classifying the complexity of constraints using finite algebras
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2005)

Constraint satisfaction problems and finite algebras
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2000)

Constraint satisfaction problems and finite algebras
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2004)

The complexity of maximal constraint languages
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2001)

The complexity of maximal constraint languages
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2001)

Quantified constraints: Algorithms and complexity
de réir: Borner, F, et al.
Foilsithe / Cruthaithe: (2003)

Quantified constraints: algorithms and complexity
de réir: Börner, F, et al.
Foilsithe / Cruthaithe: (2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2003)

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2003)

An algebraic approach to multi-sorted constraints
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2003)

An algebraic approach to multi−sorted constraints
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2003)

The complexity of constraint satisfaction games and QCSP
de réir: Boerner, F, et al.
Foilsithe / Cruthaithe: (2009)

The complexity of constraint satisfaction games and QCSP
de réir: Börner, F, et al.
Foilsithe / Cruthaithe: (2009)

Finite semigroups imposing tractable constraints
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2002)

Soft constraints: Complexity and multimorphisms
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2003)

The complexity of soft constraint satisfaction
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2006)

The complexity of soft constraint satisfaction
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2006)

Soft constraints: complexity and multimorphsims
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2003)

An algebraic characterisation of complexity for valued constraints
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2006)

An algebraic characterisation of complexity for valued constraints
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2006)

A complete classification of complexity in Allen's algebra in the presence of a non−trivial basic relation
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2001)

Algebraic structures in combinatorial problems
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2001)

Constraint satisfaction problems on intervals and lengths
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2004)

Constraint satisfaction problems on intervals and lengths
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2004)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2003)

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2003)

Constraints and Universal Algebra
de réir: P.G.Jeavons, et al.
Foilsithe / Cruthaithe: (1998)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2011)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2011)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2011)

Tractable constraints closed under a binary operation
de réir: Bulatov, A, et al.
Foilsithe / Cruthaithe: (2000)

A maximal tractable class of soft constraints
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2004)

A maximal tractable class of soft constraints
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2004)

The constraint satisfaction problem: complexity and approximability
de réir: Krokhin, A, et al.
Foilsithe / Cruthaithe: (2017)

Binarisation for valued constraint satisfaction problems
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2017)

The complexity of constraint languages
de réir: Cohen, D, et al.
Foilsithe / Cruthaithe: (2006)