Generic complexity of the membership problem for semigroups of integer matrices

DOI10.17223/20710410/55/7OpenAlexW4285292692MaRDI QIDQ5071228

Alexander N. Rybalov

Publication date: 20 April 2022

Published in: Prikladnaya Diskretnaya Matematika (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/pdm763

zbMATH Keywords

membership problemgeneric complexitysemigroups of integer matrices

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average case completeness
• A probabilistic remark on algebraic program testing
• Generic-case complexity, decision problems in group theory, and random walks.
• Mortality in Matrix Semigroups
• Generic computability, Turing degrees, and asymptotic density
• Some Questions in Computable Mathematics
• Average Case Complete Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Random Graph Isomorphism
• Binary solutions to large systems of linear equations
• Unsolvability in 3 × 3 Matrices