scientific article; zbMATH DE number 1263208

MaRDI QIDQ4234079zbMATH OpenFDO

Authors Jie Wang

Publication date 27 August 2001

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Combinatorics on words (68R15)

Recommendations

• Distributional Word Problem for Groups
• Average-case complexity and decision problems in group theory.
• Generic-case complexity, decision problems in group theory, and random walks.
• Average-case complexity of the Whitehead problem for free groups
• Space complexity and word problems of groups

Cited in

(11)

• No NP problems averaging over ranking of distributions are harder
• Generic-case complexity, decision problems in group theory, and random walks.
• Complete distributional problems, hard languages, and resource-bounded measure
• An attack on the Walnut digital signature algorithm
• Distributional Word Problem for Groups
• Matrix Transformation Is Complete for the Average Case
• Average-case intractability vs. worst-case intractability
• Rankable distributions do not provide harder instances than uniform distributions
• Reductions and convergence rates of average time
• Average-case complexity and decision problems in group theory.
• Generic case completeness

This page was built for publication:

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