Isoperimetric functions of groups and computational complexity of the word problem

DOI10.2307/3597196zbMath1026.20018arXivmath/9811106OpenAlexW2026119659WikidataQ56388581 ScholiaQ56388581MaRDI QIDQ1851485

Jean-Camille Birget, Mark V. Sapir, Alexander Yu. Ol'shanskii, Eliyahu Rips

Publication date: 5 October 2003

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9811106

zbMATH Keywords

finitely generated groupsword problemfinitely presented groupstime complexityisoperimetric functionsDehn functionsvan Kampen diagrams\(S\)-machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Cancellation theory of groups; application of van Kampen diagrams (20F06)

Related Items

Solvable groups with polynomial Dehn functions, Polynomially-bounded Dehn functions of groups, Group Embeddings with Algorithmic Properties, GROUPS WITH QUADRATIC-NON-QUADRATIC DEHN FUNCTIONS, Cheeger constants of surfaces and isoperimetric inequalities, On groups that have normal forms computable in logspace., Space functions and space complexity of the word problem in semigroups., Dehn functions of subgroups of right-angled Artin groups, Groups finitely presented in Burnside varieties, The Bounded and Precise Word Problems for Presentations of Groups, Knapsack in graph groups, Algorithmic problems in groups with quadratic Dehn function, On the difficulty of presenting finitely presentable groups., Computability Theory and Differential Geometry, THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY, Metric structures and probabilistic computation, The conjugacy problem for groups, and Higman embeddings, A strong geometric hyperbolicity property for directed graphs and monoids., CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS, Search and witness problems in group theory, The word problem of the Brin-Thompson group is \textsf{coNP}-complete, DEHN FUNCTION AND LENGTH OF PROOFS, Reductions and functors from problems to word problems, Space functions of groups, Conjugacy problem in groups with quadratic Dehn function, A Higman embedding preserving asphericity, Asymptotic invariants, complexity of groups and related problems