Homomorphisms into unary algebras

This thesis studies the computational complexity of constraint satisfaction problem (CSP) over structures with unary operations (unary algebras). We concentrate on a special class of such CSPs, so called reversing problems. We present a new proof of complexity classification for reversing problems, which uses the algebraic approach based on studying polymorphisms. We show that some reversing problems admit near unanimity polymorphisms (and are therefore solvable in polynomial time) while the remaining reversing problems do not admit weak near unanimity polymorphisms (and are therefore NP-complete)