Source author record

Dmitriy Zhuk

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.RA Computational Complexity Logic in Computer Science math.LO math.CO

Catalog footprint

Research overview

7works

5topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

QCSP monsters and the demise of the Chen Conjecture

We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language $Γ$ , QCSP $(Γ)$ , where $Γ$ is a finite language over $3$ elements which contains all constants. In particular, such problems are either in P, NP-complete, co-NP-complete or PSpace-complete. Our classification refutes the hitherto widely-believed Chen Conjecture. Additionally, we show that already on a 4-element domain there exists a constraint language $Γ$ such that QCSP $(Γ)$ is DP-complete (from Boolean Hierarchy), and on a 10-element domain there exists a constraint language giving the complexity class $Θ_{2}^{P}$ . Meanwhile, we prove the Chen Conjecture for finite conservative languages $Γ$ . If the polymorphism clone of $Γ$ has the polynomially generated powers (PGP) property then QCSP $(Γ)$ is in NP. Otherwise, the polymorphism clone of $Γ$ has the exponentially generated powers (EGP) property and QCSP $(Γ)$ is PSpace-complete.

preprint2020arXiv

Existence of cube terms in finite algebras

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.

preprint2020arXiv

Strong subalgebras and the Constraint Satisfaction Problem

In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint language $Γ$ is tractable if and only if $Γ$ is preserved by a weak near-unanimity (WNU) operation. After many efforts and partial results, this conjecture was independently proved by Andrei Bulatov and the author in 2017. In this paper we consider one of two main ingredients of my proof, that is, strong subalgebras that allow us to reduce domains of the variables iteratively. To explain how this idea works we show the algebraic properties of strong subalgebras and provide self-contained proof of two important facts about the complexity of the CSP. First, we prove that if a constraint language is not preserved by a WNU operation then the corresponding CSP is NP-hard. Second, we characterize all constraint languages that can be solved by local consistency checking. Additionally, we characterize all idempotent algebras not having a WNU term of a concrete arity $n$ , not having a WNU term, having WNU terms of all arities greater than 2. Most of the results presented in the paper are not new, but I believe this paper can help to understand my approach to CSP and the new self-contained proof of known facts will be also useful.

preprint2016arXiv

Key (critical) relations preserved by a weak near-unanimity function

In the paper we introduce a notion of a key relation, which is similar to the notion of a critical relation introduced by Keith A.Kearnes and Ágnes Szendrei. All clones on finite sets can be defined by only key relations. In addition there is a nice description of all key relations on 2 elements. These are exactly the relations that can be defined as a disjunction of linear equations. In the paper we show that, in general key relations do not have such a nice description. Nevertheless, we obtain a nice characterization of all key relations preserved by a weak near-unanimity function. This characterization is presented in the paper.

preprint2015arXiv

Switchability and collapsibility of Gap Algebras

Let A be an idempotent algebra on a 3-element domain D that omits a G-set for a factor. Suppose A is not αβ-projective (for some alpha, beta subsets of D) and is not collapsible. It follows that A is switchable. We prove that, for every finite subset Delta of Inv(A), Pol(Delta) is collapsible. We also exhibit an algebra that is collapsible from a non-singleton source but is not collapsible from any singleton source.

preprint2015arXiv

The Size of Generating Sets of Powers

In the paper we prove for every finite algebra A that either it has the polynomially generated powers (PGP) property, or it has the exponentially generated powers (EGP) property. For idempotent algebras we give a simple criteria for the algebra to satisfy EGP property.

preprint2011arXiv

The existence of a near-unanimity function is decidable

We prove that the following problem is decidable: given a finite set of relations, decide whether this set admits a near-unanimity function.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.