No label defined (Q4273608)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 475362
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 475362 |
Statements
23 May 1995
0 references
computation in permutation groups
0 references
graph isomorphism problem
0 references
intersections of permutation groups
0 references
centralizers
0 references
stabilizers
0 references
computational complexities
0 references
polynomial-time reductions
0 references
NP-complete problem
0 references
0.8169232606887817
0 references
0.7830144762992859
0 references
The author gives an actual summary of computation in permutation groups. The problems that are known to be solvable in polynomial time are collected and methods that accomplish this are indicated, moreover there are offered various proofs of polynomial time. There is also given a list of open questions, not only asking about their solvability in polynomial time, but giving the relationship amongst them. The theoretical computer science motivates attractive problems for the group theorist, for example the graph isomorphism problem. These are related to important and standard group-theoretic problems -- for example the computation of intersections of permutation groups, centralizers of elements and stabilizers of subset. As with graph isomorphisms, these problems are not considered hard in practice. While there is a large polynomial-time library, the emphasis of the paper is on problems that are related to graph isomorphisms and their group- theoretic analogues. The computational complexities of the general problems are open, though we can demonstrate polynomial-time reductions and equivalences among them. A typical approach to such issues is shown to involve an NP-complete problem. For the entire collection see [Zbl 0777.00032].
0 references