The circuit satisfaction problem CSAT(A) of an algebra A is the problem of deciding whether an equation over A (encoded by two circuits) has a solution or not. While solving systems of equations over finite algebras is either in P or NP-complete, no such dichotomy result is known for CSAT(A). In fact, Idziak, Kawalek and Krzaczkowski constructed examples of nilpotent Maltsev algebras A, for which, under the assumption of ETH and an open conjecture in circuit theory, CSAT(A) can be solved in quasipolynomial, but not polynomial time. The same is true for the circuit equivalence problem CEQV(A). In this paper we generalize their result to all nilpotent Maltsev algebras of Fitting length >2. This not only advances the project of classifying the complexity of CSAT (and CEQV) for algebras from congruence modular varieties, but we also believe that the tools we developed are of independent interest in the study of nilpotent algebras.

Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to indentify interesting classes of groups for which equation satisfiability problem is solvable in (probabilistic) polynomial-time. Based on these results, we present a full characterization of groups, for which the identity checking problem has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present full description of finite algebras from congruence modular varieties for which testing circuit equivalence can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis.

Abstract The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178(1), 253–262, 2002) where they showed that this problem is in for nilpotent groups while it is -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G/H. This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.

We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our construction of subexponential circuits of depth 2 for AND helps us to classify (modulo Exponential Time Hypothesis) modular circuits with respect to the complexity of their satisfiability. We also study a precise correlation between this complexity and the sizes of modular circuits realizing AND. In particular we use the superlinear lower bound from [10] to check satisfiability of CC0 circuits in probabilistic 2O(n/ε(n)) time, where ε is some extremely slowly increasing function. Moreover we show that AND can be computed by a polynomial size modular circuit of depth 2 (with O(log n) random bits) providing a probabilistic computational model that can not be derandomized.

The satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted either to monotone gates or linear gates. We go outside the Boolean realm and consider circuits built of any fixed set of gates on an arbitrarily large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. We want to characterize finite algebras A with a polynomial time algorithm deciding if an equation over A has a solution. We are also looking for a polynomial time algorithm deciding if two circuits over a finite algebra compute the same function. Although we have not managed to solve these problems in the most general setting we have obtained such a characterization (in terms of nice structural algebraic properties) for a very broad class of algebras from congruence modular varieties, including groups, rings, and lattices and their extensions.

In [15] a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However the problem for nilpotent (which had not been shown to be NP-hard) but not supernilpotent algebras (which had been shown to be polynomial time) remained open.

Satisfiability of Boolean circuits is among the most known and important problems in theoretical computer science. This problem is NP-complete in general but becomes polynomial time when restricted either to monotone gates or linear gates. We go outside Boolean realm and consider circuits built of any fixed set of gates on an arbitrary large finite domain. From the complexity point of view this is strictly connected with the problems of solving equations (or systems of equations) over finite algebras.

By a result of Horváth the equation solvability problem over finite nilpotent groups and rings is in P. We generalize his result, showing that the equation solvability over every finite supernilpotent Mal'cev algebra is in P. We also give an example of a nilpotent, but not supernilpotent Mal'cev algebra, whose identity checking problem is coNP-complete.

We investigate quantitative properties of BCI and BCK logics. The first part of the article compares the number of formulas provable in BCI versus BCK logics. We consider formulas built on implication and a fixed set of k variables. We investigate the proportion between the number of such formulas of a given length n provable in BCI logic against the number of formulas of length n provable in richer BCK logic. We examine an asymptotic behaviour of this fraction when length n of formulas tends to infinity. This limit gives a probability measure that randomly chosen BCK formula is also provable in BCI. We prove that this probability tends to zero as the number of variables tends to infinity. The second part of the article is devoted to the number of lambda terms representing proofs of BCI and BCK logics. We build a proportion between number of such proofs of the same length n and we investigate asymptotic behaviour of this proportion when length of proofs tends to infinity. We demonstrate that with probability 0 a randomly chosen BCK proof is also a proof of a BCI formula.

A constraint language $\Gamma$ on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by $\exists\wedge$-atomic formulas over $\Gamma$ is bounded by $\exp(O(n^k))$ for some constant k. It has recently been discovered that this property is characterized by the existence of a $(k+1)$-ary polymorphism satisfying certain identities; such polymorphisms are called k-edge operations and include Mal'cev and near-unanimity operations as special cases. We prove that if $\Gamma$ is any constraint language which, for some $k>1$, has a k-edge operation as a polymorphism, then the constraint satisfaction problem for $\langle\Gamma\rangle$ (the closure of $\Gamma$ under $\exists\wedge$-atomic expressibility) is globally tractable. We also show that the set of relations definable over $\Gamma$ using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries.

A k-edge operation \varphi on a finite set A is a k + 1-ary operation that satisfies the identities \begin{gathered} \varphi (x,x,y,...,y) \approx \varphi (x,y,x,y,...,y) \approx y, \hfill \\ \varphi (y,y,y,x,y,...,y) \approx \varphi (y,y,y,y,x,y,...,y) \approx ... \hfill \\ ... \approx \varphi (y,y,y,...,y,x) \approx y. \hfill \\ \end{gathered} We prove that any constraint language .. that, for some k \ge 1, has a k-edge operation as a polymorphism is globally tractable. We also show that the set of relations definable over .. using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries. Special instances of k-edge operations are Mal'cev and near-unanimity operations and so this class of constraint languages includes many well known examples.

Abstract The aim of this paper is to characterize varieties of Heyting algebras with decidable theory of their finite members. Actually we prove that such varieties are exactly the varieties generated by linearly ordered algebras. It contrasts to the result of Burris [2] saying that in the case of whole varieties, only trivial variety and the variety of Boolean algebras have decidable first order theories.