Distributional Word Problem for Groups

DOI10.1137/S0097539797332263zbMath0943.20027OpenAlexW1970883015MaRDI QIDQ4268708

Jie Wang

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539797332263

zbMATH Keywords

finitely presented groupsaverage-case NP-completenessdistributional word problems

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Complete on average Boolean satisfiability ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ Average-case complexity and decision problems in group theory. ⋮ On complete one-way functions

This page was built for publication: Distributional Word Problem for Groups