Fixed-class nilpotency testing problem

From Groupprops
Revision as of 17:12, 1 June 2012 by Vipul (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Definition

The fixed-class nilpotency testing problem is a general class of problems where:

  1. 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).
  2. A positive integer c is specified.
  3. We are asked to output Yes/No based on whether the group is a nilpotent group of nilpotency class at most c.

A proof version of the problem also asks, in case the group is not nilpotent of class at most c, for an explicit tuple of length c + 1 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 c, i.e., whether the group has class c but not c - 1. Here's how:

  • Reducing the precise class nilpotency testing problem for c to the fixed-class nilpotency testing problem: Check that we get a Yes for the fixed-class nilpotency testing problem for c and a No for c - 1.
  • Reducing the fixed-class nilpotency testing problem for c to the precise class nilpotency testing problem: Check that we get a Yes for at least (and hence exactly) one of the values 0,1,2,\dots,c.

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 cto the precise nilpotency class determination problem: Determine the precise nilpotency class, then check whether it exists and is less than or equal to c.

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 N 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 (O(N^{c + 1}) 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 s already given O(s^{c' + 1}) times the time taken for group multiplication plus inversion, where c' = \min \{ c ,\log_2N \} if the order of the group is known to be N, otherwise set c' = c deterministic
generating set-based black-box group algorithm for fixed-class nilpotency testing enumeration of all group elements, either already given or computable (O(N\log^2 N) 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. O(2^cc) times the maximum of O(\log_2N) 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 O(N\log N) times the time for group operations nondeterministic, requires guessing the generating set.