Classifying the complexity of constraints using finite algebras
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 |
---|---|
Format: | Journal article |
Language: | English |
Published: |
2005
|
Similar Items
-
Classifying the complexity of constraints using finite algebras
by: Bulatov, A, et al.
Published: (2005) -
Constraint satisfaction problems and finite algebras
by: Bulatov, A, et al.
Published: (2000) -
Constraint satisfaction problems and finite algebras
by: Bulatov, A, et al.
Published: (2000) -
The Complexity of Constraint Satisfaction: An Algebraic Approach
by: Krokhin, A, et al.
Published: (2004) -
The complexity of maximal constraint languages
by: Bulatov, A, et al.
Published: (2001)