A Finitely presented group whose word problem has sampleable hard instances

2016/02/07 by Robert H. Gilman, Gilman, Robert H
Computer Science · #68A20 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1602.02432

openalex publication_date 2016/02/07 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

Hard instances of natural computational problems are often elusive. In this note we present an example of a natural decision problem, the word problem for a certain finitely presented group, whose hard instances are easy to find. More precisely the problem has a complexity core sampleable in linear time.

Related

• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Complexity of some algorithmic problems in groups: a survey
• Average-case complexity and decision problems in group theory
• Generic-case complexity, decision problems in group theory and random walks
• Real Computational Universality: The Word Problem for a class of groups with infinite presentation