Distributional Word Problem for Groups

DOI10.1137/S0097539797332263MaRDI QIDQ4268708zbMATH OpenOpenAlexFDO

Authors 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

average-case NP-completenessdistributional word problemsfinitely presented groups

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)

Recommendations

• scientific article; zbMATH DE number 1263208
• Average-case complexity and decision problems in group theory.
• Generic-case complexity, decision problems in group theory, and random walks.
• Isoperimetric functions of groups and computational complexity of the word problem

Cited in

(6)

• Generic-case complexity, decision problems in group theory, and random walks.
• Complete on average Boolean satisfiability
• scientific article; zbMATH DE number 1263208 (Why is no real title available?)
• The Word Problem for Pride Groups
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268708)