Group with solvable conjugacy problem: Difference between revisions

Latest revision as of 00:39, 23 January 2012

This term is related to: combinatorial group theory
View other terms related to combinatorial group theory | View facts related to combinatorial group theory

This term is related to: geometric group theory
View other terms related to geometric group theory | View facts related to geometric group theory

Definition

Symbol-free definition

A group with solvable conjugacy problem is a finitely presented group with a finite presentation having the following property: there is an algorithm that, given any two words in the generators, can, in finite time, test whether the two words represent conjugate elements in the group.

The finite time taken depends on the word, but because the generating set is finite, there are only finitely many words of any length, so we cna obtain an upper bound on the time taken by the algorithm as a function of the length of the word.

Relation with other properties

Stronger properties

Property	Proof of implication	Intermediate notions
finitely generated free group		\|FULL LIST, MORE INFO
finitely generated abelian group		\|FULL LIST, MORE INFO
finite group		\|FULL LIST, MORE INFO
finitely presented conjugacy-separable group	finitely presented and conjugacy-separable implies solvable conjugacy problem	\|FULL LIST, MORE INFO

Weaker properties

Property	Meaning	Proof of implication	Proof of strictness (reverse implication failure)	Intermediate notions
group with solvable word problem
finitely presented group

@@ Line 15: / Line 15: @@
 ===Stronger properties===
-* [[Weaker than::Finitely generated free group]]
+{| class="sortable" border="1"
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
+|-
+| [[Weaker than::finitely generated free group]] || || || || {{intermediate notions short|group with solvable conjugacy problem|finitely generated free group}}
+|-
+| [[Weaker than::finitely generated abelian group]] || || || || {{intermediate notions short|group with solvable conjugacy problem|finitely generated abelian group}}
+|-
+| [[Weaker than::finite group]] || || || || {{intermediate notions short|group with solvable conjugacy problem|finite group}}
+|-
+| [[Weaker than::finitely presented conjugacy-separable group]] || || [[finitely presented and conjugacy-separable implies solvable conjugacy problem]] || || {{intermediate notions short|group with solvable conjugacy problem|finitely presented conjugacy-separable group}}
+|}
 ===Weaker properties===
-* [[Stronger than::Group with solvable word problem]]
+{| class="sortable" border="1"
-* [[Stronger than::Finitely presented group]]
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
+|-
+| [[Stronger than::group with solvable word problem]] || || || ||
+|-
+| [[Stronger than::finitely presented group]] || || || ||
+|}