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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01504012
Contributor : Miguel Couceiro <>
Submitted on : Saturday, April 8, 2017 - 1:17:27 AM
Last modification on : Tuesday, December 18, 2018 - 4:38:02 PM
Long-term archiving on : Sunday, July 9, 2017 - 12:12:30 PM

File

maximal_partial_subclones_revi...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01504012, version 1

Collections

Citation

Miguel Couceiro, Lucien Haddad, Victor Lagerkvist, Biman Roy. On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations. 47th IEEE International Symposium on Multiple-Valued Logic (ISMVL), May 2017, Novi Sad, Serbia. ⟨hal-01504012⟩

Share

Metrics

Record views

613

Files downloads

108