6 citations · 20 across the 15 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019
QCSP monsters and the demise of the Chen Conjecture
Dmitriy Zhuk, Barnaby Martin
We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language , QCSP, where is a fin…
math.RA2019
Existence of cube terms in finite algebras
Alexandr Kazda, Dmitriy Zhuk
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 su…
math.LO2019
Deciding the existence of minority terms
Alexandr Kazda, Jakub Opršal, Matt Valeriote +1
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation that satisfies the minority equations $m(y,x,…