Search and witness problems in group theory.

DOI10.1515/GCC.2010.015zbMATH Open1222.20024arXiv1010.0382OpenAlexW2963744260MaRDI QIDQ3085996FDOQ3085996

Authors: Vladimir Shpilrain 

Publication date: 1 April 2011

Published in: Groups - Complexity - Cryptology (Search for Journal in Brave)

Abstract: Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. On the other hand, witness problems are: given a property P and an object O with the property P, find a proof of the fact that O indeed has the property P. On the third hand(?!), search problems are of the following nature: given a property P and an object O with the property P, find something "material" establishing the property P; for example, given two conjugate elements of a group, find a conjugator. In this survey our focus is on various search problems in group theory, including the word search problem, the subgroup membership search problem, the conjugacy search problem, and others.

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

Recommendations

• scientific article; zbMATH DE number 67424
• Decision problems for 3-manifolds and their fundamental groups
• scientific article
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3897215

zbMATH Keywords

stratificationdecision problemssearch problemsconjugacy search problemalgorithmic problemssubgroup membership search problemword search problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Research exposition (monographs, survey articles) pertaining to group theory (20-02) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• ALGORITHMIC PROBLEMS IN VARIETIES
• Authentication from matrix conjugation
• Generic-case complexity, decision problems in group theory, and random walks.
• Automorphic orbits in free groups.
• Counting words of minimum length in an automorphic orbit.
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• Isoperimetric functions of groups and computational complexity of the word problem
• Relations among the squares of the generators of the braid group
• Isoperimetric and isodiametric functions of groups
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Average-case complexity and decision problems in group theory.
• Extended Nielsen transformations and triviality of a group

Cited In (6)

• Two general schemes of algebraic cryptography
• Algorithmic problems in Engel groups and cryptographic applications
• Asymptotic invariants, complexity of groups and related problems.
• The power conjugacy search problem in a cyclic subgroup in groups with the condition \(C(3)\) \& \(T(6)\).
• The status of polycyclic group-based cryptography: a survey and open problems
• Search problems in groups and branching processes.

This page was built for publication: Search and witness problems in group theory.

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