Upcoming meeting:
-
Meeting #211
Alexander Treyer
(Math Center in Akademgorodok)"Equationally noetherian graphs and hypergraphs"
Abstract. A simple graph is called equationally noetherian if any system of equations is equivalent to its finite subsystem. It isn't hard to notice that a simple graph is equationally noetherian if and only if it is equationally noetherian in one variable equations. Based on this property we described all equationally noetherian graphs with help of forbidden subgraphs (joint with Ivan Buchinsky). Also several examples of hypergraphs will be presented that are not equationally noetherian but equationally noetherian in one variable equations.
Latest announcements:
-
Meeting #210
Armin Weiss
(Stuttgart University)"Hardness of equations over finite solvable groups under the exponential time hypothesis"
Abstract. The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in 2002. They showed that this problem is in polynomial time for nilpotent groups, while it is \(NP\)-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\). In this talk I will show that such normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails. Moreover, the same hardness result applies to the equation identity problem. The talk is based on joint work with Pawel Idziak, Piotr Kawalek, and Jacek Krzaczkowski.
-
Meeting #209
Alexander Rybalov
(Sobolev Institute of Mathematics, Omsk, Russia)"Generic complexity of the identity problem over finite groups and semigroups"
Abstract. The problem of checking identities in algebraic structures is the one of the most fundamental problem in algebra. For finite algebraic structures this problem can be decidable in polynomial time, or hard (co-\(NP\)-complete). In this talk I present generic polynomial algorithms for the identity problem in all finite groups and for some monoids and semigroups. These algorithms work in the cases when the problem is co-\(NP\)-complete.
-
Meeting #208
Vladimir Remeslennikov
(Sobolev Institute of Mathematics, Omsk, Russia)"Relative quasivarieties of Hasse diagrams with a single zero"
Abstract. The present work is devoted to the category of Artinian partially ordered sets \(K\) (\(APOS\)), which is defined as follows: any strictly decreasing chain of elements terminates at a finite number.
-
Meeting #207
Alexander Treyer
(Sobolev Institute of Mathematics, Omsk, Russia)"Centralizer dimension and equationally noetherian groups"
Abstract. In 1999th G.Baumslag, A.Miasnikov and V.Remeslennikov formulated the following problem:
Let \(L\) be the language of group theory, \(G\) be a group and \(L_G\) be the language of group theory with a set of constants from the group \(G\). Let the group \(G = <G, L_G>\) be equationally noetherian over one variable equations (\(1\)-equationally noetherian) Does it follow that the group \(G\) is equationally noetherian?
An example of a nilpotent group will be presented, which is \(1\)-equationally noetherian but is not equationally noetherian in general. The proof will be based on the new results on a close relation between the concepts of centralizer dimension and noetherenes by equations for groups. -
Meeting #206
Alexander Rybalov
(Sobolev Institute of Mathematics, Omsk, Russia)"Generic complexity of the subset sum problem for some semigroups"
Abstract.The subset sum problem is a classical combinatorial problem, studied for many decades. This problem is very popular in cryptography, where there are many cryptosystems based on it. Myasnikov, Nikolaev and Ushakov in 2015 introduced analogs of the subset sum problem for arbitrary groups (semigroups). They explored the computational complexity of these problems for various groups: polynomial solvability is proved for hyperbolic groups, \(NP\)-completeness is proved for Baumslag-Solitar groups. In this talk I present results about generic polynomial decidability of the subset sum problem for following semigroups: monoid \(Mat(N,k)\) of \(k\) x \(k\) matrices with natural entries, monoid \(SL(N,2)\) of unimodular \(2\)x\(2\) matrices with natural entries, groups \(PSL(Z,2)\) and \(SL(Z,2)\), and some Brandt semigroups.
-
Meeting #205
Alexei Miasnikov
(Stevens Institute)"The Diophantine problem in classical matrix groups"
Abstract.The Diophantine problem in a group (ring) \(G\) is decidable if there exists an algorithm that given a finite system of equations with coefficients in \(G\) decides whether or not the system has a solution in \(G\). I will discuss the Diophantine problem in the groups the classical matrix groups \(G_n(R)\), where \(R\) is an associative unitary ring, \(n > 2\), and \(G(n,R)\) is one of the groups \(GL(n,R)\), \(SL(n,R)\), \(T(n,R)\), \(UT(n,R)\), \(PGL(n,R)\), or \(PSL(n,R)\) (in the last two cases we assume that \(R\) is also commutative). The main result is that the Diophantine problem in \(G(n,R)\) with a chosen set of coefficients is Ptime reducible (Karp reducible) to the Diophantine problem in R with respect to a suitable set of coefficients in \(R\). What is much more interesting is that the converse is also true. In the case when the ring \(R\) is finitely generated and commutative the result above allows one to clarify the situation completely, modulo a big conjecture in number theory. For not finitely generated rings, more so for uncountable rings, decidability of the Diophantine problem heavily depends on the set of constants. The case of classical fields of reals, complex and p-adic numbers is especially interesting, as well as the rings of p-adic integers (which is related to pro- p completions of groups). I am going to touch on this subject and, if time permits, show some surprising examples. The talk is based on joint results with Mahmood Sohrabi.