Пятница, 26 октября, ауд. 203. Начало в 17:00.
Докладчик: Mika Hirvensalo (University of Turku).
Тема: Undecidability and complexity issues on integer matrices.
Abstract
For a finite alphabet A, a well known embedding $A^* \times A^*$ to $3 \times 3$ integer matrices implies a lot of undecidability results on $3 \times 3$ integer matrices. Various constructions allow to establish the undecidability on a small number of matrices, even though the size of matrices has to be increased.
On the other hand, we cannot construct an embedding $A^* \times A^*$ to $2 \times 2$ integer matrices, and consequently there are no analogous undecidability results for $2 \times 2$ matrices. On the contrary, many problems known undecidable can be shown decidable for $2 \times 2$ integer matrices. However, the complexities of such problems are not studied very well. It can be shown that the identity problem and the mortality problem for $2 \times 2$ matrices are NP-hard. (Joint work with Paul Bell and Igor Potapov)
