Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAL'TSEV OPERATION:
Reports tagged with Mal'tsev operation:
TR02-034 | 18th April 2002
Andrei Bulatov

Mal'tsev constraints are tractable

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>




ISSN 1433-8092 | Imprint