Classifying the complexity of constraints using finite algebras

Classifying the complexity of constraints using finite algebras

Show other versions (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...

书目详细资料
Main Authors:	Bulatov, A, Jeavons, P, Krokhin, A
格式:	Journal article
语言:	English
出版:	2005

相似书籍

Classifying the complexity of constraints using finite algebras
由: Bulatov, A, et al.
出版: (2005)

Constraint satisfaction problems and finite algebras
由: Bulatov, A, et al.
出版: (2000)

Constraint satisfaction problems and finite algebras
由: Bulatov, A, et al.
出版: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
由: Krokhin, A, et al.
出版: (2004)

The complexity of maximal constraint languages
由: Bulatov, A, et al.
出版: (2001)

The complexity of maximal constraint languages
由: Bulatov, A, et al.
出版: (2001)

Quantified constraints: Algorithms and complexity
由: Borner, F, et al.
出版: (2003)

Quantified constraints: algorithms and complexity
由: Börner, F, et al.
出版: (2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
由: Krokhin, A, et al.
出版: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
由: Krokhin, A, et al.
出版: (2003)

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra
由: Krokhin, A, et al.
出版: (2003)

An algebraic approach to multi-sorted constraints
由: Bulatov, A, et al.
出版: (2003)

An algebraic approach to multi−sorted constraints
由: Bulatov, A, et al.
出版: (2003)

The complexity of constraint satisfaction games and QCSP
由: Boerner, F, et al.
出版: (2009)

The complexity of constraint satisfaction games and QCSP
由: Börner, F, et al.
出版: (2009)

Finite semigroups imposing tractable constraints
由: Bulatov, A, et al.
出版: (2002)

Soft constraints: Complexity and multimorphisms
由: Cohen, D, et al.
出版: (2003)

The complexity of soft constraint satisfaction
由: Cohen, D, et al.
出版: (2006)

The complexity of soft constraint satisfaction
由: Cohen, D, et al.
出版: (2006)

Soft constraints: complexity and multimorphsims
由: Cohen, D, et al.
出版: (2003)

An algebraic characterisation of complexity for valued constraints
由: Cohen, D, et al.
出版: (2006)

An algebraic characterisation of complexity for valued constraints
由: Cohen, D, et al.
出版: (2006)

A complete classification of complexity in Allen's algebra in the presence of a non−trivial basic relation
由: Krokhin, A, et al.
出版: (2001)

Algebraic structures in combinatorial problems
由: Bulatov, A, et al.
出版: (2001)

Constraint satisfaction problems on intervals and lengths
由: Krokhin, A, et al.
出版: (2004)

Constraint satisfaction problems on intervals and lengths
由: Krokhin, A, et al.
出版: (2004)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
由: Krokhin, A, et al.
出版: (2003)

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
由: Krokhin, A, et al.
出版: (2003)

Constraints and Universal Algebra
由: P.G.Jeavons, et al.
出版: (1998)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
由: Cohen, D, et al.
出版: (2011)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
由: Cohen, D, et al.
出版: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
由: Cohen, D, et al.
出版: (2011)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
由: Cohen, D, et al.
出版: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
由: Cohen, D, et al.
出版: (2011)

Tractable constraints closed under a binary operation
由: Bulatov, A, et al.
出版: (2000)

A maximal tractable class of soft constraints
由: Cohen, D, et al.
出版: (2004)

A maximal tractable class of soft constraints
由: Cohen, D, et al.
出版: (2004)

The constraint satisfaction problem: complexity and approximability
由: Krokhin, A, et al.
出版: (2017)

Binarisation for valued constraint satisfaction problems
由: Cohen, D, et al.
出版: (2017)

The complexity of constraint languages
由: Cohen, D, et al.
出版: (2006)