2
votes
0answers
31 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
1
vote
1answer
33 views

Complexity of the Automorphism problem in group with polynomial growth.

Do we have any characterization of groups with a decidable automorphism problem ? When it is decidable, Is there any results about the complexity of the automorphism problem in group with polynomial ...
8
votes
1answer
115 views

Finding the smallest set on which a group acts faithfully

Given a finite group $G$, how efficient can one make an algorithm to find the size of the smallest set $S$ such that $G$ is isomorphic to a group of permutations of the members of $S$? And does the ...
2
votes
0answers
48 views

Abelian SubGroup Variant:

Consider the following problem: Find integers $x_1, x_2, x_3,\dots, x_n$ Such that: $$P(x_1,x_2,\dots, x_n) = Q$$ for some integer $Q$ and polynomial $P$ where for all permutations of any set of ...
2
votes
0answers
107 views

Comparing two character tables

Suppose that you are given two finite groups, for example, via their Cayley tables. One can efficiently compute their character tables (efficiently = polynomial time in the order of the group), this ...
8
votes
1answer
176 views

Applications of computation on very large groups

I have been studying computational group theory and I am reading and trying to implement these algorithms. But what that is actually bothering me is, what is the practical advantage of computing all ...
1
vote
0answers
140 views

Does there exist a group (finitely presented) such that the isomorphism problem for the group and the trivial group is undecidable?

It is well known that the isomorphism problem for finitely presented groups is unsolvable. That is to say that if $G$ and $G'$are both fp- groups, then in general it is impossible to provide an ...
5
votes
1answer
200 views

Complexity of finite group isomorphism problem

Consider the next decision problem: Given two finite groups represented by their multiplicity table, determine if they are isomorphic or not. Clearly, this problem belongs to NP since given a witness ...