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

For a finite group $G$, the size of a minimum generating set of $G$ isdenoted by $d(G)$. Given a finite group $G$ and an integer $k$, deciding if$d(G)\leq k$ is known as the minimum generating set (MIN-GEN) problem.  A group $G$ of order $n$ has generating set of size $\lceil \log_p n \rceil$where $p$ is the smallest prime dividing $n=|G|$. This fact is used to designan $n^{\log_p n+O(1)}$-time algorithm for the group isomorphism problem ofgroups specified by their Cayley tables (attributed to Tarjan by Miller, 1978).The same fact can be used to give an $n^{\log_p n+O(1)}$-time algorithm for theMIN-GEN problem. We show that the MIN-GEN problem can be solved in time$n^{(1/4)\log_p n+O(1)}$ for general groups given by their Cayley tables. Thisruntime incidentally matches with the runtime of the best known algorithm forthe group isomorphism problem.  We show that if a group $G$, given by its Cayley table, is the product ofsimple groups then a minimum generating set of $G$ can be computed in timepolynomial in $|G|$.  Given groups $G_i$ along with $d(G_i)$ for $i\in [r]$ the problem ofcomputing $d(\Pi_{i\in[r]} G_i)$ is nontrivial. As a consequence of our resultfor products of simple groups we show that this problem also can be solved inpolynomial time for Cayley table representation.  For the MIN-GEN problem for permutation groups, to the best of our knowledge,no significantly better algorithm than the brute force algorithm is known. Foran input group $G\leq S_n$, the brute force algorithm runs in time $|G|^{O(n)}$which can be $2^{\Omega(n^2)}$. We show that if $G\leq S_n$ is a primitivepermutation group then the MIN-GEN problem can be solved in timequasi-polynomial in $n$.  We also design a $\mathrm{DTIME}(2^n)$ algorithm for computing a minimumgenerating set of permutation groups all of whose non-abelian chief factorshave bounded orders.

Algorithms for the Minimum Generating Set Problem