COMPLEXITY, CRYPTOGRAPHY, AND
COMBINATORIAL GROUP THEORY
Jean-Camille Birget
Dept. of Computer Science, Rutgers University - Camden
Friday, December 8th, 2000, 11:00am-12:00pm
Library/CATT Building, Room LC102, Brooklyn Campus
Complexity theory and cryptography are rich in unsolved problems that
have been open for a long time, so it is interesting to look for related
problems in other fields.
Combinatorial group theory is the study of (usually infinite) groups
presented by generators and relations. When a group is given by a finite
set of generators, every group element is represented by words over an
alphabet (the alphabet being the generators and their inverses).
The most fundamental decision problem in combinatorial group theory is
the "word problem" (for a fixed group with fixed set of generators):
Given two words over the above alphabet, do they represent the same
element of the group?
The word problem of groups has close connections with the theory of
computation:
- Every decision problem is linear-time reducible to a word problem (of
some finitely generated group), with almost the same complexity (time, or
space, deterministic, nondet., or co-nondet.).
- On the other hand, complexity (and decidability, etc.) of the word
problem is an algebraic invariant (it does not change significantly under
change of generators for the same group). There are nice algebraic
characterizations of semi-decidability and of decidability of the word
problem (Higman 1961, Boone-Higman 1976).
- Over the last few years, Sapir, Olshanskii, Rips and I have obtained a
simple characterization of nondeterministic time complexity for the word
problem and, in particular, of NP. This connects nondeterministic time and
the "isoperimetric function" of a group, and gives a group-theoretic
description of NP.
- The transformation groups introduced by R. Thompson (in the 1960s)
lead
to coNP-complete word problems. There may be interesting connections with
cryptography: The Thompson groups are defined as transformations of
bit-strings, and every finite permutation of bit-strings (of any length)
is in the Thompson groups; it might be possible to use the Thompson groups
to construct one-way functions.
For further information, please contact Nasir Memon
