Log-trimmable subgroup description rule

From Groupprops
Jump to: navigation, search

This article defines a property that can be evaluated for a subgroup description rule, viz a rule for describing a subgroup of a group given an encoding


BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]

Definition

A subgroup description rule is said to be log-trimmable if there is an algorithm that, given any log-size encoding of a group, and a description of a subgroup using the subgroup description rule, outputs a description of the subgroup that is polynomial in the log-size, such that the time taken by the algorithm is bounded by a polynomial in the log-size and in the size of the original subgroup description.

Relation with other properties

Weaker properties