The set of minimal braids is co-NP-complete

DOI10.1016/0196-6774(91)90011-MMaRDI QIDQ3348424zbMATH OpenOpenAlexFDO

Authors

Publication date 1991

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(91)90011-m

zbMATH Keywords

braid groupminimal braids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• In search of minimal random braid configurations
• Braid group cohomologies and algorithm complexity
• scientific article; zbMATH DE number 4078810
• Braid representatives minimizing the number of simple walks
• Minimum crossing numbers for 3-braids
• Braiding minimal sets of vector fields
• Coxeter systems for which the Brink-Howlett automaton is minimal
• scientific article; zbMATH DE number 503389
• scientific article; zbMATH DE number 18526
• Minimal pairs and complete problems

Cited in

(13)

• A fast method for comparing braids
• Attack on Kayawood protocol: uncloaking private keys
• Efficient solutions to the braid isotopy problem.
• Finite-time braiding exponents
• Composition problems for braids
• A NOTE ON CLOSED 3-BRAIDS
• Mean-set attack: cryptanalysis of Sibert et al. authentication protocol
• Strong law of large numbers on graphs and groups
• An attack on the Walnut digital signature algorithm
• In search of minimal random braid configurations
• Logspace computations in graph products
• The word problem for Artin groups of FC type
• A new approach to the word and conjugacy problems in the braid groups

This page was built for publication: The set of minimal braids is co-NP-complete

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