The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Distributional Word Problem for Groups
Jie Wang,
Pages. 1264-1283
Abstract
Contents 1. Introduction
2. Preliminaries
2.1. Average polynomial time
2.2. Polynomial-time reductions
2.3. Polynomial-time computable distributions
2.4. Uniform distributions
2.5. Distribution controlling lemma
3. Finitely presented groups and word problems
4. Undecidable word problem for groups
5. Main theorem
5.1. Dynamic coding scheme
5.2. Semigroup construction
5.3. Group construction and the reduction
6. Some related results
6.1. Worst-case NP-complete word problem
6.2. Isomorphisms of average-case NP-complete problems
Key words verage-case NP-completeness, finitely presented groups, word problem
Mathmatical Subject Classification 68Q15, 20F05, 20F10, 03D40