On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations

摘要

A strong partial clone is a set of partial operations closed under composition and containing all partial projections. Let X be the set of all Boolean strong partial clones whose total operations are the projections. This set is of practical interest since it induces a partial order on the complexity of NP-complete constraint satisfaction problems. In this paper we study X from the algebraic point of view, and prove that there exists two intervals in X, corresponding to natural constraint satisfaction problems, such that one is at least countably infinite and the other has the cardinality of the continuum.