All Questions
Tagged with gr.group-theory word-problem
7 questions
28
votes
5
answers
4k
views
Are there any computational problems in groups that are harder than P?
There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).
Then there are several classes of groups like ...
- 391
14
votes
1
answer
764
views
Finite-dimensional version of the word problem for groups
The (uniform) word problem for groups can be stated in several equivalent ways:
Word Problem for Groups (WP)
Instance: A finite presentation of a group G and an element w of G as a product of ...
- 1,959
7
votes
1
answer
251
views
Asymptotics of the number of required Dehn relators in hyperbolic groups
If $G = \langle X | R \rangle$ is a $\delta$-hyperbolic group presentation, then Dehn's algorithm provides a linear time solution to the word problem, but the linear constant is horribly exponential ...
- 565
5
votes
2
answers
489
views
The generalized word problem on groups
Given some group $G$ that is generated by $a$ and $b$, each of which has infinite order, and some free subgroup $N$ generated by $a^k$ and $b^k$, is there any algorithm that tells me if some $x \in G$ ...
- 469
2
votes
1
answer
232
views
Examples of group families with solvable uniform word problem
I would like to know of any examples of families of groups that are known (or conjectured) to have a solvable uniform word problem, i.e. an algorithm that given a presentation $P$ of a group in the ...
- 1,936
2
votes
0
answers
219
views
Occurrence problem for commutator subgroup
The occurrence problem asks if, given a group $G$ and a subgroup $H$ of $G$, there exists an algorithm to decide whether $x\in G$ belongs to $H$.
Let $G$ be a group that has solvable word problem.
Is ...
- 115
1
vote
1
answer
259
views
Which properties can be read off the balls of a Cayley graph?
For which properties (P) [of groups] does the following hold:
given a group $G$ which has a finite presentation with at most $n$ relations of length at most $\ell$, there is a $R(n,\ell)$ so that, if ...
- 4,432