scientific article; zbMATH DE number 475362
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].
- Algorithms for matrix groups and the Tits alternative
- Bases for primitive permutation groups and a conjecture of Babai
- Computing transformation semigroups
- Monte Carlo circuits for the abelian permutation group intersection problem
- On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
- Primitive normalisers in quasipolynomial time
- Computing normalisers of intransitive groups
- Space efficient representations of finite groups
- Colored hypergraph isomorphism is fixed parameter tractable
- Finding fixed point free elements and small bases in permutation groups
- Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
- Algorithms for permutability in finite groups.
- Graph Isomorphism is in SPP
- Computing the soluble radical of a permutation group.
- Public-key cryptography and invariant theory
- Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
- Coset closure of a circulant S-ring and schurity problem
- Exploiting symmetries in polyhedral computations
- A name abstraction functor for named sets
- Families of symmetries as efficient models of resource binding
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- Graphs of bounded treewidth can be canonized in AC^1
- A linear-time algorithm for the orbit problem over cyclic groups
- Algebraic cryptography: new constructions and their security against provable break
- Expanding Generating Sets for Solvable Permutation Groups
- \textit{xTras}: a field-theory inspired \textit{xAct} package for Mathematica
- A Logspace Algorithm for Partial 2-Tree Canonization
- The parallel complexity of graph canonization under abelian group action
- The Parallel Complexity of Abelian Permutation Group Problems
- scientific article; zbMATH DE number 4057755 (Why is no real title available?)
- Groups acting on tensor products.
- scientific article; zbMATH DE number 96386 (Why is no real title available?)
- scientific article; zbMATH DE number 96388 (Why is no real title available?)
- scientific article; zbMATH DE number 123361 (Why is no real title available?)
- scientific article; zbMATH DE number 1263311 (Why is no real title available?)
- scientific article; zbMATH DE number 1004935 (Why is no real title available?)
- Computational indistinguishability between quantum states and its cryptographic application
- scientific article; zbMATH DE number 2151233 (Why is no real title available?)
- Circulant graphs: recognizing and isomorphism testing in polynomial time
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- Using symmetry to optimize over the Sherali-Adams relaxation
- scientific article; zbMATH DE number 841570 (Why is no real title available?)
- Nominal Unification and Matching of Higher Order Expressions with Recursive Let
- Algorithms for group isomorphism via group extensions and cohomology
- Polynomial-time normalizers
- Algorithmic Problems for Metrics on Permutation Groups
- Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- Computing the subgroups of a permutation group
- A nonadaptive NC checker for permutation group intersection
- A Faster Isomorphism Test for Graphs of Small Degree
- Comparison of Atom Maps
- Symmetries, local names and dynamic (de)-allocation of names
- On the complexity of matroid isomorphism problem
- Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
- The minimal faithful permutation degree of groups without abelian normal subgroups
- Complexity of identifying fitting-free groups
- Equational reasoning modulo commutativity in languages with binders
- Exploiting the symmetry of \(\mathbb{Z}^n\): randomization and the automorphism problem
- Membership problems in finite groups
- Computational group theory: bedrock and new frontiers
- On p-group isomorphism: search-to-decision, counting-to-decision and nilpotency class reductions via tensors
- On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness
- Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms
- Finding a cycle base of a permutation group in polynomial time
- AI Planning Languages Semantics
- Verified SAT-Based AI Planning
- Upper Bounding Diameters of State Spaces of Factored Transition Systems
- Membership and conjugacy in inverse semigroups
- SZK proofs for black-box group problems
- On the asymmetric complexity of the group-intersection problem
- Isomorphism and canonization of tournaments and hypertournaments
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4273608)