Journal article icon

Journal article

Classifying the complexity of constraints using finite algebras

Abstract:

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 forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the prope...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1137/S0097539700376676
Journal:
SIAM JOURNAL ON COMPUTING More from this journal
Volume:
34
Issue:
3
Pages:
720-742
Publication date:
2005-01-01
DOI:
EISSN:
1095-7111
ISSN:
0097-5397
Language:
English
Keywords:
Pubs id:
pubs:328487
UUID:
uuid:f7eb31eb-3daa-4d9c-af30-8acc09dfa7cf
Local pid:
pubs:328487
Source identifiers:
328487
Deposit date:
2013-11-16

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP