English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The worst-case complexity of group-theoretic algorithms has been studied fora long time. Generic-case complexity, or complexity on random inputs, wasintroduced and studied relatively recently. In this paper, we address theaverage-case time complexity of the word problem in several classes of groupsand show that it is often the case that the average-case complexity is linearwith respect to the length of an input word. The classes of groups that weconsider include groups of matrices over rationals (in particular, polycyclicgroups), some classes of solvable groups, as well as free products. Along theway, we improve several bounds for the worst-case complexity of the wordproblem in groups of matrices, in particular in nilpotent groups. For freeproducts, we also address the average-case complexity of the subgroupmembership problem and show that it is often linear, too. Finally, we discusscomplexity of the identity problem that has not been considered before.

Linear average-case complexity of algorithmic problems in groups