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 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

      Identifiers

      0 references
      0 references
      0 references
      0 references