Polynomial-Time Algorithms for Permutation Groups.

Abstract

A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this procedure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techiques have wide applicability and have recently been used to improve many graph isomorphism algorithms. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1980
Accession Number
ADA097825

Entities

People

  • Eugene Luks
  • John Hopcroft
  • Merrick Furst

Organizations

  • Department of Computer Science, Cornell University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Contracts
  • Generators
  • Graph Theory
  • Identities
  • Inclusions
  • Mathematics
  • Military Research
  • New York
  • Pennsylvania
  • Permutations
  • Polynomials
  • Sequences
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.