Classifying the complexity of constraints using finite algebras

Classifying the complexity of constraints using finite algebras

Показать другие версии (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...

Полное описание

Библиографические подробности
Главные авторы:	Bulatov, A, Jeavons, P, Krokhin, A
Формат:	Journal article
Язык:	English
Опубликовано:	2005

Схожие документы

Classifying the complexity of constraints using finite algebras
по: Bulatov, A, и др.
Опубликовано: (2005)

Constraint satisfaction problems and finite algebras
по: Bulatov, A, и др.
Опубликовано: (2000)

Constraint satisfaction problems and finite algebras
по: Bulatov, A, и др.
Опубликовано: (2000)

The Complexity of Constraint Satisfaction: An Algebraic Approach
по: Krokhin, A, и др.
Опубликовано: (2004)

The complexity of maximal constraint languages
по: Bulatov, A, и др.
Опубликовано: (2001)

The complexity of maximal constraint languages
по: Bulatov, A, и др.
Опубликовано: (2001)

Quantified constraints: Algorithms and complexity
по: Borner, F, и др.
Опубликовано: (2003)

Quantified constraints: algorithms and complexity
по: Börner, F, и др.
Опубликовано: (2003)

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
по: Krokhin, A, и др.
Опубликовано: (2003)

Functions of multiple−valued logic and the complexity of constraint satisfaction: A short survey
по: Krokhin, A, и др.
Опубликовано: (2003)

Structural Theory of Automata‚ Semigroups‚ and Universal Algebra
по: Krokhin, A, и др.
Опубликовано: (2003)

An algebraic approach to multi-sorted constraints
по: Bulatov, A, и др.
Опубликовано: (2003)

An algebraic approach to multi−sorted constraints
по: Bulatov, A, и др.
Опубликовано: (2003)

The complexity of constraint satisfaction games and QCSP
по: Boerner, F, и др.
Опубликовано: (2009)

The complexity of constraint satisfaction games and QCSP
по: Börner, F, и др.
Опубликовано: (2009)

Finite semigroups imposing tractable constraints
по: Bulatov, A, и др.
Опубликовано: (2002)

Soft constraints: Complexity and multimorphisms
по: Cohen, D, и др.
Опубликовано: (2003)

The complexity of soft constraint satisfaction
по: Cohen, D, и др.
Опубликовано: (2006)

The complexity of soft constraint satisfaction
по: Cohen, D, и др.
Опубликовано: (2006)

Soft constraints: complexity and multimorphsims
по: Cohen, D, и др.
Опубликовано: (2003)

An algebraic characterisation of complexity for valued constraints
по: Cohen, D, и др.
Опубликовано: (2006)

An algebraic characterisation of complexity for valued constraints
по: Cohen, D, и др.
Опубликовано: (2006)

A complete classification of complexity in Allen's algebra in the presence of a non−trivial basic relation
по: Krokhin, A, и др.
Опубликовано: (2001)

Algebraic structures in combinatorial problems
по: Bulatov, A, и др.
Опубликовано: (2001)

Constraint satisfaction problems on intervals and lengths
по: Krokhin, A, и др.
Опубликовано: (2004)

Constraint satisfaction problems on intervals and lengths
по: Krokhin, A, и др.
Опубликовано: (2004)

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
по: Krokhin, A, и др.
Опубликовано: (2003)

Reasoning about temporal relations : the tractable subalgebras of Allen's interval algebra
по: Krokhin, A, и др.
Опубликовано: (2003)

Constraints and Universal Algebra
по: P.G.Jeavons, и др.
Опубликовано: (1998)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
по: Cohen, D, и др.
Опубликовано: (2011)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
по: Cohen, D, и др.
Опубликовано: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
по: Cohen, D, и др.
Опубликовано: (2011)

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
по: Cohen, D, и др.
Опубликовано: (2010)

An algebraic theory of complexity for valued constraints: Establishing a Galois connection
по: Cohen, D, и др.
Опубликовано: (2011)

Tractable constraints closed under a binary operation
по: Bulatov, A, и др.
Опубликовано: (2000)

A maximal tractable class of soft constraints
по: Cohen, D, и др.
Опубликовано: (2004)

A maximal tractable class of soft constraints
по: Cohen, D, и др.
Опубликовано: (2004)

The constraint satisfaction problem: complexity and approximability
по: Krokhin, A, и др.
Опубликовано: (2017)

Binarisation for valued constraint satisfaction problems
по: Cohen, D, и др.
Опубликовано: (2017)

The complexity of constraint languages
по: Cohen, D, и др.
Опубликовано: (2006)