Questions tagged [group-theory]
The group-theory tag has no summary.
49 questions
1
vote
0
answers
64
views
Can the group-structure of my constraint reduce the corresponding assignment problem to polynomial time search complexity?
Consider a finite Abelian group $G$ where each element is its own inverse. As an explicit example, let $G$ be the integers 0 to 31 under the bitwise XOR $\oplus$ operation. We have a collection of $n$ ...
- 11
0
votes
0
answers
25
views
Standards for storing computer readable description of finite groups
Finite Groups are groups which act on finite sets. They occour in many areas of computer science.
There are many way to define a group such as
defining the undelying set, the group operation, the ...
- 225
0
votes
1
answer
69
views
How hard is it to find the order of an element in a finite abelian group of unknown order?
In short, I want to find the complexity theoretic hardness of the problem of finding the order of any element in a group of unknown order.
Let, $n$ denotes an input parameter and the complexity ...
1
vote
1
answer
100
views
How to motivate freshman students towards automatic groups?
I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automatic groups.
I'm very experienced as a ...
- 111
0
votes
0
answers
23
views
How to motivate freshman students towards automata groups? [duplicate]
I'm a new professor and working at a computer science college. I'm going to be responsible for giving a one-hour lecture to motivate my students to study automata groups.
I'm very experienced as a ...
- 111
1
vote
0
answers
58
views
Is the HSP with the symmetric group exactly equivalent to the Graph Isomorphism problem?
It is well known that an algorithm to solve the Hidden Subgroup Problem (HSP) with the symmetric group can solve the Graph isomorphism problem.
But is this true in reverse? Will an algorithm for graph ...
- 327
0
votes
2
answers
71
views
Doubt regarding conjugations of permutations
I was studying the Barrington Theorem in https://homes.cs.washington.edu/~anuprao/pubs/CSE531Sp2020/lecture2.pdf when I found a doubt regarding permutations. Particularly, with conjugations.
It is ...
- 559
4
votes
2
answers
472
views
Paint a Cube by rolling it (Puzzle Algorithm)
I stumbled across this game in Simon Tatham's puzzle app. It's called cube. The description according to the game is:
You have a grid of 16 squares, six of which are blue; on one square rests a cube. ...
- 143
0
votes
1
answer
87
views
Logic Programming - A definite program for the theory of groups
I am studying theoretical computer science using Ayala's book "Fundamentos da Programação Lógica e Funcional" (the book is written in Portuguese), but the part I am studying right now is ...
- 320
1
vote
1
answer
84
views
Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
0
votes
1
answer
98
views
Efficient algorithm/data structure that maps tic-tac-toe boards to floats
I'm implementing a q-learning agent for tic-tac-toe that requires mapping from tic-tac-toe boards to float values. Since certain game states are equivalent and should have the same value, it would be ...
1
vote
0
answers
55
views
matching vector families that form a group
Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)?
You can find the definition of MV families here:
https://homes....
- 21
1
vote
1
answer
64
views
Number of binary words that form a group of Hamming weight at most d
Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
- 21
1
vote
1
answer
54
views
Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?
Let $R = \{\emptyset,a,\epsilon\}$ (the elements here are regular expressions) and let $+$ be the or operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an ...
- 13
3
votes
1
answer
141
views
Iteratively enumerating all permutations of $N$ objects using a generating set
The group theory of $S_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math....
- 133