| dc.contributor.author |
Lucchini, Andrea |
|
| dc.contributor.author |
Thakkar, Dhara |
|
| dc.coverage.spatial |
United States of America |
|
| dc.date.accessioned |
2023-07-04T08:17:36Z |
|
| dc.date.available |
2023-07-04T08:17:36Z |
|
| dc.date.issued |
2023-06 |
|
| dc.identifier.citation |
Lucchini, Andrea and Thakkar, Dhara, "The minimum generating set problem", arXiv, Cornell University Library, DOI: arXiv:2306.07633, Jun. 2023. |
|
| dc.identifier.uri |
http://arxiv.org/abs/2306.07633 |
|
| dc.identifier.uri |
https://repository.iitgn.ac.in/handle/123456789/8938 |
|
| dc.description.abstract |
Let G be a finite group. In order to determine the smallest cardinality d(G) of a generating set of G and a generating set with this cardinality, one should repeat many times the test whether a subset of G of small cardinality generates G. We prove that if a chief series of G is known, then the numbers of these generating tests can be drastically reduced. At most |G|13/5 subsets must be tested. This implies that the minimum generating set problem for a finite group G can be solved in polynomial time. |
|
| dc.description.statementofresponsibility |
by Andrea Lucchini and Dhara Thakkar |
|
| dc.language.iso |
en_US |
|
| dc.publisher |
Cornell University Library |
|
| dc.subject |
Smallest cardinality |
|
| dc.subject |
Cardinality generates G |
|
| dc.subject |
polynomial time |
|
| dc.subject |
NP |
|
| dc.title |
The minimum generating set problem |
|
| dc.type |
Article |
|
| dc.relation.journal |
arXiv |
|