Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Universal algebra:
TR05-028 | 12th February 2005
Elmar Böhler

On the Lattice of Clones Below the Polynomial Time Functions

A clone is a set of functions that is closed under generalized substitution.
The set FP of functions being computable deterministically in polynomial
time is such a clone. It is well-known that the set of subclones of every
clone forms a lattice. We study the lattice below FP, which ... more >>>

TR05-036 | 28th March 2005
Hubie Chen

Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>>

TR07-025 | 5th March 2007
Benoit Larose, Pascal Tesson, Pascal Tesson

Universal Algebra and Hardness Results for Constraint Satisfaction Problems

We present algebraic conditions on constraint languages \Gamma
that ensure the hardness of the constraint satisfaction problem
CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL.
These criteria also give non-expressibility results for various
restrictions of Datalog. Furthermore, we show that if
CSP(\Gamma) is not first-order definable then it ... more >>>

TR07-093 | 27th July 2007
Andrei A. Bulatov

The complexity of the counting constraint satisfaction problem

Revisions: 1

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite
relational structure H can be expressed as follows: given a
relational structure G over the same vocabulary,
determine the number of homomorphisms from G to H.
In this paper we characterize relational structures H for which
#CSP(H) can be solved in ... more >>>

TR14-066 | 17th April 2014
Suguru Tamaki, Yuichi Yoshida

Robust Approximation of Temporal CSP

A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>>

ISSN 1433-8092 | Imprint