# Conjugacy-separable and all homomorphisms to any finite group can be listed in finite time implies solvable conjugacy problem

Suppose is a finitely generated group that is both a conjugacy-separable group and a finitely generated group for which all homomorphisms to any finite group can be listed in finite time. Then, is a group with solvable conjugacy problem.

## Related facts

### Similar facts

### Applications

- Finitely presented and residually finite implies solvable word problem (obtained by combining with finitely presented implies all homomorphisms to any finite group can be listed in finite time)

## Proof

### Proof outline

Note that in order to solve the conjugacy problem, it is sufficient to come up with an algorithm that can, in finite time, show that two given words do *not* represent conjugate elements if indeed they does not. This is because there already exists an algorithm (for *every* finitely generated group) that can show in finite time that two given words *do* represent conjugate elements.

The algorithm is as follows:

- Consider the list of all finite groups up to isomorphism. Enumerate them as .
- For each : Construct the list of all homomorphisms from to (possible by assumption on ). For each homomorphism, evaluate the image of the two words under the homomorphism as elements of . If the images are not conjugate in , then return that the word does
*not*represent the identity element of .

Since is conjugacy-separable, it is the case that for any two non-conjugate elements, there exists a finite quotient where their . This finite quotient equals some , so homomorphisms to will detect that the two elements are not conjugate. Thus, for two non-conjugate elements, the algorithm returns in finite time that they are not conjugate.

Note that unlike the analogous result for residually finite groups, it is not possible here in general to simply consider a countable collection of finite groups such that every finite group embeds in one of them, because the embedding need not be as a conjugacy-closed subgroup.