Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options answers only
not deleted
user 35840
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
12
votes
Decidability in groups
Many of the undecidable properties of finitely presented groups are verifiable i.e. if they are true, then they can be proved true. Such properities include trivial, finite, abelian, nilpotent, free, …
- 37.4k
11
votes
Accepted
Identifying a group without 2-torsion
Using a mixture of computation and thought I believe that I have established that this group is indeed torsion-free. I don't know of any general approach to solving that particular problem. Even if th …
- 37.4k
10
votes
Accepted
Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|...
It is also worth mentioning that although these algorithms both involve backtrack searches, in practice the difficulties tend to arise from large output size when the index if big rather than from the …
- 37.4k
2
votes
Finding a basis for the (linear combinations) span of a matrix group, efficiently?
The MeatAxe algorithm (which is available in GAP and Magma) can be used to solve (1). It is very fast in practice and I think it computes a decompostion into irreducibles in time $O(n^4)$ in the copr …
- 37.4k
6
votes
Accepted
Complexity of establishing finite groups (non)-isomorphism ?
It is unknown whether this problem is polynomial. It is at worst $O(N^{\log N})$. To see that, observe that the group can be generated by at most $\log N$ elements, a homomorphism is determined by the …
- 37.4k
27
votes
Accepted
Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?
Devising practical algorithms for problems of this type is certainly an active area of research within the computational group theory community. …
- 37.4k
12
votes
Algorithm for reducing words in a Coxeter group
An algorithm for reducing arbitrary words in any Coxeter group to their lexicographically least reduced representatives is described in the paper:
B. Brink and R.B. Howlett,
``A finiteness property a …
- 37.4k
10
votes
Two groups acting on a set.
Added later: It should also be mentioned that the implementations of the above algorithms in GAP and Magma involve backtrack searches, and so are potentially exponential, but in practice they run fast …
- 37.4k
6
votes
Accepted
Complexity of decision problem to decide if permutation group is $k$-transitive
There have been several articles on this forum discussing these topics, but here is a quick review.
A base $B$ for a subgroup $G \le {\rm Sym}(X)$ is a sequence $(\alpha_1,\ldots,\alpha_k)$ of points …
- 37.4k
3
votes
Accepted
Complexity to decide for permutation group if every element fixed at most $k$ points
As I said in my comment, this problem is easily seen to be in P for fixed $k$, because we can compute all $(k+1)$-point stabilizers in polynomial time.
So let's assume that $k$ is part of the input.
…
- 37.4k
1
vote
Accepted
Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
The paper by Holt, Leedham-Green and O'Brien is geared more towards finding practical algorithms, and the $\mathtt{CompositionTree}$ function in Magma is very effective and improving all the time. …
- 37.4k
10
votes
Accepted
Time Complexity of the Word Problem for Finite Permutation Groups
As has been pointed out in comments, you cannot hope to do better in general than $O(n(l_1+l_2))$, where $n$ is the degree of the permutation groups and $l_1$, $l_2$ are the lengths of the words.
But …
- 37.4k