The membership problem for subsemigroups of GL2(Z) is NP-complete.
Paul C. BellMika HirvensaloIgor PotapovPublished in: Inf. Comput. (2024)
Keyphrases
- np complete
- np hard
- randomly generated
- computational complexity
- satisfiability problem
- constraint satisfaction problems
- polynomially solvable
- conjunctive queries
- pspace complete
- phase transition
- data complexity
- polynomial time complexity
- database
- computationally complex
- bounded treewidth
- similarity measure
- decision trees
- machine learning
- real world