Laboratory of Mathematical Logic at PDMI

Пятница, 10 июля, ауд. 106. Начало в 13:00.

Докладчик: Mika Hirvensalo (University of Turku).

Тема: On the computational complexity of small-dimensional integer matrix problems.

Abstract

Because of commutativity, the computational problems appear very simple in dimension one, whereas Paterson's result from 1970 shows that already in dimension three, there are undecidable integer matrix problems. Apparently, the studies in dimension two have been conducted only relatively recently. The study in dimension two opens a variety of interesting problems: It will be pointed out that, for example, the membership problem (suitably restricted) for semigroups is NP-hard, whereas the corresponding problem for groups is in P. The recent progress on the complexity upper bounds in two-dimensional case is also reviewed.

It will be interesting to note that the decidability (and the complexity) results in dimension two utilize the algebraic structure of PSL_2(Z): Roughly speaking, it is possible to present a (restricted) 2 times 2 integer matrix as a sequence over a finite alphabet (with relations), and hence transfer results from language theory into matrix theory.