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 generators and their inverses.  

*Question*: Does every linear representation of G in a (not necessarily finite-dimensional) Hilbert space map w to the identity operator?  

*Equivalently*: Does every unitary representation of G in a Hilbert space map w to the identity operator?  

*Equivalently*: Does every normal subgroup of G contain w?  

*Equivalently*: Is w=1 in G?


As is well-known, WP is undecidable; more specifically, it belongs to RE∖coRE, where [RE](http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re) is the class of recursively enumerable languages and [coRE](http://qwiki.stanford.edu/wiki/Complexity_Zoo:C#core) is the class of their complements. (In fact, it is known that WP remains undecidable even if we fix the group G and its finite presentation suitably, but that is not the topic of this question.)


We can consider the finite-dimensional version of WP.


**Finite-Dimensional Word Problem for Groups (FWP)**  

*Instance*: Same as WP.  

*Question*: Does every *matrix* representation of G map w to the identity matrix?  

*Equivalently*: Does every unitary *matrix* representation of G map w to the identity matrix?  

*Equivalently*: Does every normal subgroup of G *of finite index* contain w?  

(The equivalence is based on a result by Malcev; see [this post](https://mathoverflow.net/questions/9628/finitely-presented-sub-groups-of-gln-c/9635#9635) by Greg Kuperberg and the comments attached to it.)


The two problems have different answers for some instances; that is, sometimes w≠1 in G but every matrix representation maps w to the identity matrix. There even exists a finitely presented infinite group which does not have a nontrivial matrix representation. See the answers to the question “[Finitely presented sub-groups of GL(n,C)](https://mathoverflow.net/questions/9628/finitely-presented-sub-groups-of-gln-c)” by Dmitri.


In fact, FWP is in coRE unlike WP: if we also give the dimension as part of the input, the problem becomes decidable (because it is a system of algebraic equations over ℂ), and therefore FWP can be put in coRE by trying all dimensions.



> 
> **Question**: Is FWP decidable?
> 
> 
> 


I do not even know whether FWP is NP-hard or not. As far as I know, FWP can be in P or undecidable, or anywhere in between!


(Note: FWP can be viewed as a (very) special case of the problem discussed in the question “[Decidability of matrix algebra](https://mathoverflow.net/questions/33879/decidability-of-matrix-algebra)” by Ricky Demer.)



Finite-dimensional version of the word problem for groups
FWP is undecidable by a [result of Slobodskoi.](https://doi.org/10.1007/BF01735740) Slobodskoi shows that the "Universal theory" of finite groups is undecidable. What you are asking for is whether the "Q-theory" of the pseudovariety of finite groups is decidable. The universal theory and Q-theory are equivalent for the pseudovariety of finite groups (see [Kharlampovich-Sapir](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.766), section 2.4 for a discussion), so the Q-theory is undecidable too.


