On the Computational Complexity of Matrix Semigroup Problems

• Autorzy: Bell P. C. , Potapov I.
• Języki publikacji: EN

Abstrakty

EN

Most computational problems for matrix semigroups and groups are inherently difficult to solve and even undecidable starting from dimension three. The questions about the decidability and complexity of problems for two-dimensional matrix semigroups remain open and are directly linked with other challenging problems in the field. In this paper we study the computational complexity of the problem of determining whether the identity matrix belongs to a matrix semigroup (the Identity Problem) generated by a finite set of 2 × 2 integral unimodular matrices. The Identity Problem for matrix semigroups is a well-known challenging problem, which has remained open in any dimension until recently. It is currently known that the problem is decidable in dimension two and undecidable starting from dimension four. In particular, we show that the Identity Problem for 2 × 2 integral unimodular matrices is NP-hard by a reduction of the Subset Sum Problem and several new encoding techniques. An upper bound for the nontrivial decidability result by C. Choffrut and J. Karhum¨aki is unknown. However, we derive a lower bound on the minimum length solution to the Identity Problem for a constructible set of instances, which is exponential in the number of matrices of the generator set and the maximal element of the matrices. This shows that the most obvious candidate for an NP algorithm, which is to guess the shortest sequence of matrices which multiply to give the identity matrix, does not work correctly since the certificate would have a length which is exponential in the size of the instance. Both results lead to a number of corollaries confirming the same bounds for vector reachability, scalar reachability and zero in the right upper corner problems.

Słowa kluczowe

EN

computational complexity; Identity Problem; matrix semigroups

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 1--13
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Bell P. C.

autor

Potapov I.

• Department of Computer Science, Loughborough University, Loughborough, LE11 3TU, UK,

Bibliografia

• [1] Ang, T., Pighizzini, G., Rampersad, N., Shallit, J.: Automata and reduced words in the free group, arXiv:0910.4555, 2009.
• [2] Babai, L., Beals, R., Cai, J.-Y., Ivanyos, G., Luks, E. M.: Multiplicative equations over commuting matrices, Proc. of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 96, 1996.
• [3] Beaudry,M.: Membership testing in commutative transformation semigroups, Information and Computation, 79(1), October 1988, 84-93.
• [4] Bell, P. C., Potapov, I.: On undecidability bounds for matrix decision problems, Theoretical Computer Science, 391(1-2), 2008, 3-13.
• [5] Bell, P. C., Potapov, I.: Periodic and infinite traces in matrix semigroups, Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS 4910, 2008, 148-161.
• [6] Bell, P. C., Potapov, I.: Reachability problems in quaternion matrix and rotation semigroups, Information and Computation, 206(11), 2008, 1353-1361.
• [7] Bell, P. C., Potapov, I.: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups, International Journal of Foundations of Computer Science, 21(6), 2010, 963-978.
• [8] Birget, J.-C., Margolis, S.: Two-letter group codes that preserve aperiodicity of inverse finite automata, Semigroup Forum, 76(1), 2008, 159-168.
• [9] Blondel, V., Tsitsiklis, J.: When is a pair of matrices mortal?, Information Processing Letters, 63, 1997, 283-286.
• [10] Blondel, V. D., Cassaigne, J., Karhumäki, J.: Problem 10.3, Freeness of multiplicative matrix semigroups, Unsolved Problems inMathematical Systems and Control Theory (V. D. Blondel, A.Megretski, Eds.), Princeton University Press, 2004.
• [11] Blondel, V. D., Portier, N.: The presence of a zero in an integer linear recurrent sequence is NP-hard to decide, Linear Algebra and its Applications, 2002, 91-98.
• [12] Bournez, O., Branicky,M.: On the mortality problem for matrices of low dimensions, Theory of Computing Systems, 35(4), 2002, 433-448.
• [13] Cai, J.-Y., Fuchs, W. H., Kozen, D., Liu, Z.: Efficient average-case algorithms for the modular group, The 35th Annual Symposium on Foundations of Computer Science (FOCS), 1994.
• [14] Cai, J.-Y., Liu, Z.: The boundedmembership problemof the monoid SL2(N), Mathematical Systems Theory, 29(6), 1996, 573-587.
• [15] Cassaigne, J., Harju, T., Karhumäki, J.: On the undecidability of freeness of matrix semigroups, International Journal of Algebra and Computation, 9(3-4), 1999, 295-305.
• [16] Cassaigne, J., Karhumäki, J.: Examples of undecidable problems for 2-generator matrix semigroups, Theoretical Computer Science, 204(1-2), 1998, 29-34.
• [17] Cassaigne, J., Nicolas, F.: On the decidability of semigroup freeness, arXiv:0808.3112v2 [cs.DM], September 2008.
• [18] Choffrut, C., Karhumäki, J.: Some decision problems on integer matrices, Informatics and Applications, 39, 2005, 125-131.
• [19] Gawrychowski, P., Gutan, M., Kisielewicz, A.: On the problem of freeness of multiplicative matrix semigroups, Theoretical Computer Science, 411(7-9), February 2010, 1115-1120.
• [20] Gurevich, Y., Schupp, P.: Membership problem for the modular group, SIAM J. Comput., 37(2), 2007, 425-459.
• [21] Halava, V., Harju, T., Hirvensalo, M.: Undecidability bounds for integer matrices using Claus instances, International Journal of Foundations of Computer Science (IJFCS), 18,5, 2007, 931-948.
• [22] Halava, V., Harju, T., Hirvensalo,M., Karhumäki, J.: Skolem's problem - on the border between decidability and undecidability, TUCS Technical Report Number 683, 2005.
• [23] Halava, V., Hirvensalo, M.: Improved matrix pair undecidability results, Acta Informatica, 44(3-4), 2007, 191-205.
• [24] Harju, T.: Post correspondence problemand small dimensionalmatrices, Lecture Notes in Computer Science, LNCS 5583, 2009, 39-46.
• [25] Lyndon, R. C., Schupp, P. E.: Combinatorial Group Theory, Springer-Verlag, 1977.
• [26] Mihailova, A.: The occurrence problem for a direct product of groups, Doklady Akademii Nauk, 119(in Russian), 1958, 1103-1105.