---
tag: 4AF7AF7690
kind: problem
name: Conjugacy problem
msc: ["20F10", "03D40"]
uses: [082DWWXMRJ, 0DXD4QSZ8A, 0JGEQXQ4AC]
about: [0DXD4QSZ8A, 082DWWXMRJ]
sources:
  - url: https://en.wikipedia.org/wiki/Conjugacy_problem
same_as:
  wikidata: Q5161137
  wikipedia: Conjugacy problem
history:
  posed_by: "Max Dehn"
  first_stated: "1911"
---

## Problem

Let $G$ be a [[finitely generated group|082DWWXMRJ]] with a finite generating set $S$.
A word is a finite sequence of elements of $S$ and their inverses.
The *conjugacy problem* for $G$ asks for an algorithm that takes two words $u$ and $v$ and decides whether they represent [[conjugate|0DXD4QSZ8A]] elements of $G$.
That is, the algorithm decides whether $v = g u g^{-1}$ in $G$ for some $g \in G$.

## Remarks

Whether the problem is solvable does not depend on the finite generating set.
A word $w$ represents the identity if and only if it is conjugate to the empty word.
So an algorithm for the conjugacy problem solves the [[word problem|PBGTTAVMMT]], and every group with unsolvable word problem has unsolvable conjugacy problem.
The converse fails: there are finitely presented groups with solvable word problem and unsolvable conjugacy problem.

The problem is solvable in many classes of groups.
In a [[free group|0KTW26C80J]], two elements are conjugate if and only if their cyclically reduced forms are cyclic permutations of each other.
It is also solvable for finitely generated abelian groups, where it is the word problem, for [[hyperbolic groups|JWJ8YPR7EB]], and for [[braid groups|BNR4H5GCTP]].
It is one of the three decision problems, with the word problem and the [[isomorphism problem|MP3F49QT3C]], that Max Dehn posed for groups given by presentations.

## Explanations

### L1 human

Two elements of a group are conjugate when one becomes the other after a change of point of view, $v = g u g^{-1}$.
The conjugacy problem asks whether a computer can always decide this for a group given by generators.
In a free group the answer is easy: cancel what you can, also around the ends of the word, and compare the results up to rotation.
For example, in the free group on $a$ and $b$, the word $b a b^{-1}$ reduces cyclically to $a$, so it is conjugate to $a$ and not to $b$.