Homomorphism-checking problem (generating sets)

This article describes a basic decision problem in computational group theory

Description

Given data

Groups $G_{1}$ and $G_{2}$ are specified by means of encodings $C_{1}$ and $C_{2}$ respectively. We are given a generating set $A_{1}$ of $G_{1}$ and a map $f:A_{1}\to G_{2}$.

Goal

We want to know whether there is a homomorphism $\phi :G_{1}\to G_{2}$ that extends $f$ (such a homomorphism, if it exists must be unique).

Relation with other problems

Related problems

• Isomorphism-checking problem
• Automorphism-checking problem
• Endomorphism-checking problem

Solution

If such a homomorphism doesn't exist, that means that the problem arises because there is a word in the elements of $A_{1}$ that reduces to the identity, but such that the word in their corresponding images does not reduce to the identity in $G_{2}$. Hence, if we can somehow guess what that word is, then evaluating the word will not be hard.

Of course, the length of the word may itself be quite large, but we know that there exists a small circuit that outputs any given word.

The upshot is that the homomorphism-checking problem is in nondeterministic polynomial time.