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 computational-complexity
Search options answers only not deleted user 35840
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Kolmogorov Complexity and so on.
8 votes
Groups whose word problem can be solved in constant time
This is a long comment rather than an answer. Using the ideas in the examples that you gave, you could show that any group that is virtually a direct product of finitely many free groups of finite ra …
- 38.4k
15 votes
Testing whether two elements of $\text{SL}(2, \mathbb{F}_{2^n})$ generate the entire group
The answer to your question is yes. The subgroups of ${\rm SL}(2,q)$ were classified by Dickson in 1901 (and probably earlier). For more general questions about subgroups of ${\rm GL}(n,q)$, there is …
- 38.4k
10 votes
Accepted
Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|...
I guess I should try and answer that! I don't really have a good answer to the question of why the random method is not mentioned in the book, and I would agree that it might to be the fastest method …
- 38.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 …
- 38.4k
20 votes
Accepted
Is the Normal centralizer problem in P?
Yes. This is Proposition 7.3 of Eugene M. Luks. Permutation groups and polynomial-time computation. Pages 139-175 of: Larry Finkelstein and William M. Kantor, editors. Groups and Computation, Volume …
- 38.4k
20 votes
Accepted
How to compute all irreducible representations of a finite group ? (how GAP is doing this?)
You seem to be asking for a description of the the algorithms in computational representation theory. I think that is far too broad a question for this site and you need to be more specific. There is …
- 38.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 …
- 38.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. …
- 38.4k
1 vote
Accepted
Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
In the paper Holt, D., Leedham-Green, C. R., & O'Brien EA (2020). Constructing composition factors for a linear group in polynomial time. JOURNAL OF ALGEBRA, 561, 215-236. 10.1016/j.jalgebra.2020.02.0 …
- 38.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 …
- 38.4k
29 votes
Accepted
Are there any computational problems in groups that are harder than P?
An earlier reference for groups with this property is J. Avenhaus and K. Madlener. Subrekursive Komplexität der Gruppen. I. Gruppen mit vorgeschriebenen Komplexität. Acta Infomat., 9 (1): 87-104, 197 …
- 38.4k