Search

Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently promise CSPs, we propose an algebraic framework for valued promise CSPs. To every valued promise CSP we associate an algebraic object, its so-called valued minion. Our main result shows that the existence of a homomorphism between the associated valued minions implies a polynomial-time reduction between the original CSPs. We also show that this general reduction theorem includes important inapproximability results, for instance, the inapproximability of almost solvable systems of linear equations beyond the random assignment threshold.

For relational structures A, B of the same signature, the Promise Constraint Satisfaction Problem PCSP(A,B) asks whether a given input structure maps homomorphically to A or does not even map to B. We are promised that the input satisfies exactly one of these two cases. If there exists a structure C with homomorphisms $A\to C\to B$, then PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that some PCSPs over finite structures A, B require solving CSPs over infinite C. We show that even when such a reduction to finite C is possible, this structure may become arbitrarily large. For every integer $n>1$ and every prime p we give A, B of size n with a single relation of arity $n^p$ such that PCSP(A, B) reduces via a chain of homomorphisms $ A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In a second family of examples, for every prime $p\geq 7$ we construct A, B of size $p-1$ with a single ternary relation such that PCSP(A, B) reduces via $A\to C\to B$ to a tractable CSP over some C of size p but not over any smaller structure. In contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This extends results and answers a question of Deng et al.

For some Maltsev conditions $\Sigma$ it is enough to check if a finite algebra $\mathbf A$ satisfies $\Sigma$ locally on subsets of bounded size, in order to decide, whether $\mathbf A$ satisfies $\Sigma$ (globally). This local-global property is the main known source of tractability results for deciding Maltsev conditions. In this paper we investigate the local-global property for the existence of a $G$-term, i.e. an $n$-ary term that is invariant under permuting its variables according to a permutation group $G \leq$ Sym($n$). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local-global property (and thus can be decided in polynomial time), while symmetric terms of arity $n>2$ fail to have it., Comment: 22 pages

We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given finite algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations., Comment: 17 pages, number n fixed to k in the proof of Lemma 11

We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most $N$, where the number $N$ depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on $N$ that, in the special case of algebras with more than $\binom{|A|}2$ basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a $k$-ary near unanimity operation if and only if it contains a $k$-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation., Comment: 29 pages

This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation $m$ that satisfies the minority equations $m(y,x,x) \approx m(x,y,x) \approx m(x,x,y) \approx y$. We show that a common polynomial-time approach to testing for this type of condition will not work in this case and that this decision problem lies in the class NP.

It is known that any finite idempotent algebra that satisfies a nontrivial Maltsev condition must satisfy the linear one-equality Maltsev condition (a variant of the term discovered by M. Siggers and refined by K. Kearnes, P. Markovi\'c, and R. McKenzie): \[ t(r,a,r,e)\approx t(a,r,e,a). \] We show that if we drop the finiteness assumption, the $k$-ary weak near unanimity equations imply only trivial linear one-equality Maltsev conditions for every $k\geq 3$. From this it follows that there is no nontrivial linear one-equality condition that would hold in all idempotent algebras having Taylor terms. Miroslav Ol\v{s}\'ak has recently shown that there is a weakest nontrivial strong Maltsev condition for idempotent algebras. Ol\v{s}\'ak has found several such (mutually equivalent) conditions consisting of two or more equations. Our result shows that Ol\v{s}\'ak's equation systems can't be compressed into just one equation., Comment: 9 pages

In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition $\Sigma$. Our goal in this paper is to show that $\Sigma$-testing can be accomplished in polynomial time when the algebras tested are idempotent and the Maltsev condition $\Sigma$ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of J\'onsson (or Gumm) terms of fixed length., Comment: 33 pages, 19 figures

The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even $\Delta$-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even $\Delta$-matroids, we then extend the tractability result to larger classes of $\Delta$-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely co-independent, compact, local, linear and binary, with the following caveat: we represent $\Delta$-matroids by lists of tuples, while the last two use a representation by matrices. Since an $n\times n$ matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary $\Delta$-matroids., Comment: 33 pages, 9 figures

We characterize absorption in finite idempotent algebras by means of J\'onsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.

We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspace). At the moment, it is not known for which structures $\mathbb A$ will CSP($\mathbb A$) be solvable by a linear Datalog program. However, once somebody obtains a characterization of linear Datalog, our result immediately gives a characterization of symmetric Datalog.

We prove that every congruence distributive variety has directed J\'{o}nsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original J\'{o}nsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in CD and CM varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and $k$-permutable for some $k$., Comment: 17 pages

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence also to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups., Comment: 12 pages

We prove that whenever A is a 3-conservative relational structure with only binary and unary relations then the algebra of polymorphisms of A either has no Taylor operation (i.e. CSP(A) is NP-complete), or generates a congruence meet semidistributive variety (i.e. CSP(A) has bounded width)., Comment: 9 pages, 3 figures

We prove that if A is a large random relational structure with at least one relation of arity at least 2 then the problem EXT(A) is almost surely NP-complete., Comment: 8 pages

We prove that when a digraph $G$ has a Maltsev polymorphism, then $G$ also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev graphs and the complexity of the Constraint Satisfaction Problem., Comment: 8 pages, 4 figures; minor changes (stylistics, elsarticle LaTeX style, citations); submitted to European Journal of Combinatorics

The paper gives a characterisation of the chain relation of a sofic subshift. Every sofic subshift $\Sigma$ can be described by a labelled graph $G$. Factorising $G$ in a suitable way we obtain the graph $G/_\approx$ that offers insight into some properties of the original subshift. Using $G/_\approx$ we describe first the chain relation in $\Sigma$, then characterise chain-transitive sofic subshifts, chain-mixing sofic subshifts and finally the attractors of the subshift dynamic system. At the end we present (straightforward) algorithms deciding chain-transitivity and chain-mixing properties of a sofic subshift and listing all the attractors of the subshift system., Comment: 14 pages, 9 figures, preprint (final version published in Fundamenta Informaticae)

We investigate the continuity of the \omega-functions and real functions defined by weighted finite automata (WFA). We concentrate on the case of average preserving WFA. We show that every continuous \omega-function definable by some WFA can be defined by an average preserving WFA and then characterize minimal average preserving WFA whose \omega-function or \omega-function and real function are continuous. We obtain several algorithmic reductions for WFA-related decision problems. In particular, we show that deciding whether the \omega-function and real function of an average preserving WFA are both continuous is computationally equivalent to deciding stability of a set of matrices. We also present a method for constructing WFA that compute continuous real functions., Comment: 41 pages, 9 figures

Moebius number systems represent points using sequences of Moebius transformations. Thorough the paper, we are mainly interested in representing the unit circle (which is equivalent to representing R\cup\{\infty\}). The main aim of the paper is to improve already known tools for proving that a given subshift--iterative system pair is in fact a Moebius number system. We also study the existence problem: How to describe iterative systems resp. subshifts for which there exists a subshift resp. iterative system such that the resulting pair forms a Moebius number system. While we were unable to provide a complete answer to this question, we present both positive and negative partial results. As Moebius number systems are also subshifts, we can ask when a given Moebius number system is sofic. We give this problem a short treatment at the end of our paper., Comment: 50 pages, 13 figures