Abstract
SL 2(N) is the set of all 2 × 2 matrices with nonnegative integer entries and determinant 1. The bounded membership problem (BMN) ofSL 2(N) is that given a subsetS ofSL 2(N), a matrixA εSL 2(N), and an integern, whetherA can be represented as a product of at mostn matrices (repetitions are allowed) inS. We prove that BMN is NP-complete, but its randomized version under natural distribution is solvable in average polynomial time. Furthermore, it is proved that if the number of elements ofS is a constant, then BMN is polynomial time computable.
Similar content being viewed by others
References
A. Blass and Y. Gurevich. Matrix Decomposition Is Complete for the Average Case. To appear inSIAM Journal of Computing.
J. Cai, W. H. J. Fuchs, D. Kozen and Z. Liu. Efficient Average-Case Algorithms for the Modular Group. InProceedings of the 35th Annual Symposium on Foundations of Computer Science (1994), 143–152.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest.Introduction to Algorithms. MIT Press, 1990.
M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
Y. Gurevich. Matrix Decomposition Problem Is Complete for the Average Case. InProceedings of the 31stAnnual Symposium on Foundations of Computer Science. IEEE Computer Society Press, 1990, pp. 802–811.
Y. Gurevich. Average Case Completeness.Journal of Computer and System Sciences, 42:3 (1991), 346–398.
G. H. Hardy and E. M. Wright.An Introduction to the Theory of Numbers. Oxford University Press, 5th edn. 1988 printing.
L. Levin. Average Case Complete Problems.SIAM Journal of Computing, 15 (1986), 285–286.
R. Lyndon and P. Schupp,Combinatorial Group Theory. Springer-Verlag, 1977.
W. Magnus, A. Karrass, and D. Solitar,Combinatorial Group Theory. Interscience, 1966.
A. C. Yao and D. E. Knuth. Analysis of the Subtractive Algorithm for Greatest Common Divisors.Proceedings of the National Academy of Sciences, USA, 72:12 (1975), 4720–4722.
Author information
Authors and Affiliations
Additional information
J. Cai was supported in part by NSF Grants CCR 9057486 and CCR 9319093, and an Alfred P. Sloan Fellowship. Z. Liu was supported in part by NSF Grant CCR 9057486.
Rights and permissions
About this article
Cite this article
Cai, J., Liu, Z. The bounded membership problem of the monoidSL 2(N). Math. Systems Theory 29, 573–587 (1996). https://doi.org/10.1007/BF01301965
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01301965