Home

Пятница 26 октября, 17-00, ауд. 203

Пятница, 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)