Fixed-class nilpotency testing problem
Contents
Definition
The fixed-class nilpotency testing problem is a general class of problems where:
- A group is specified using some suitable group description rule (which may be an encoding, multi-encoding, or description using a presentation, among other possibilities).
- A positive integer is specified.
- We are asked to output Yes/No based on whether the group is a nilpotent group of nilpotency class at most .
A proof version of the problem also asks, in case the group is not nilpotent of class at most , for an explicit tuple of length of elements of the group for which the iterated left-normed commutator is not the identity.
Equivalent problems
Testing whether a given group has precisely a given nilpotency class
The above problem is equivalent to the precise class nilpotency testing problem: determining whether the nilpotency class of a given group is precisely , i.e., whether the group has class but not . Here's how:
- Reducing the precise class nilpotency testing problem for to the fixed-class nilpotency testing problem: Check that we get a Yes for the fixed-class nilpotency testing problem for and a No for .
- Reducing the fixed-class nilpotency testing problem for to the precise class nilpotency testing problem: Check that we get a Yes for at least (and hence exactly) one of the values .
Determination of precise nilpotency class
The above problem is also equivalent to the problem of determining the precise nilpotency class as follows:
- Reducing the precise nilpotency class determination problem to the fixed-class nilpotency testing problem: Do the fixed-class nilpotency testing for 1,2,3,... and stop as soon as you get a Yes.
- Reducing the fixed-class nilpotency testing problem for class to the precise nilpotency class determination problem: Determine the precise nilpotency class, then check whether it exists and is less than or equal to .
Algorithms
Black-box group algorithms
These work for a group specified by means of an encoding.
Algorithm | Additional information needed for algorithm, if any | Time taken, where is the order of the group | Type of algorithm |
---|---|---|---|
brute-force black-box group algorithm for fixed-class nilpotency testing | enumeration of all group elements, either already given or computable | ( times the time taken for group multiplication plus inversion) plus (time taken for enumeration of elements) | deterministic |
black-box group algorithm for fixed-class nilpotency testing given a generating set | generating set of size already given | times the time taken for group multiplication plus inversion, where if the order of the group is known to be , otherwise set | deterministic |
generating set-based black-box group algorithm for fixed-class nilpotency testing | enumeration of all group elements, either already given or computable | ( times the time taken for group multiplication) plus (time taken for enumeration of elements) | deterministic |
randomized black-box group algorithm for fixed-class nilpotency testing | ability to sample uniformly at random from the group. Note that a generic random number generator, along with a full enumeration of group elements, can achieve this. | times the maximum of and the time for group operations | randomized, with No answers always being correct but the Yes answers possibly being wrong. This puts the problem in co-RP. |
nondeterministic black-box group algorithm for fixed-class nilpotency testing | enumeration of all group elements | times the time for group operations | nondeterministic, requires guessing the generating set. |