> it’s undecidable to compute if two finitely-presented groups are isomorphic.
But (iirc) it is semidecidable, like the halting problem, and isomorphism is decidable for finitely presented abelian groups.
But (iirc) it is semidecidable, like the halting problem, and isomorphism is decidable for finitely presented abelian groups.
Do you have a favorite example that highlights the unique computational properties of vector spaces?
*I don't know how this changes in the finitely-presented case, but I assume the extra constraint can be used to improve the performance of the algorithms. It's a lot easier to find asymptotic analysis of the finitely-generated case though and I don't see a way around dealing with the fact that it's still not free.
[0] - I'm basing this on Chapter 8 of https://cs.uwaterloo.ca/~astorjoh/diss2up.pdf, but this is a deep field in which I am not an expert, so if you are, I'd love to hear more.