ALCOMFT-TR-03-53

A. Krokhin and B. Larose
Solving order constraints in logarithmic space
Warwick. Work package 4. October 2003.

Abstract: We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions on a poset which guarantee solvability of the problems in (deterministic, symmetric, or non-deterministic) logarithmic space.

On the example of order constraints we study how a certain algebraic invariance property is related to solvability of a constraint satisfaction problem in non-deterministic logarithmic space.

keywords: complexity, constraint satisfaction, poset retraction, logspace complexity classes, transitive closure logics, polymorphisms.

Postscript file: ALCOMFT-TR-03-53.ps.gz (140 kb).