Search and witness problems in group theory.

DOI10.1515/GCC.2010.015MaRDI QIDQ3085996zbMATH OpenOpenAlexFDO

Authors Vladimir Shpilrain

Publication date 1 April 2011

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

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

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)

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.

Recommendations

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

Cites work

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

Cited in

(6)

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

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)