Leírás
University of Szeged, Bolyai Institute, Algebra Seminar
Abstract. Let $A$ be a fixed finite algebra with finitely many basic operations. The Subpower Membership Problem for $A$ is the following combinatorial decision problem SMP(A):
Input: $k+1$ elements $a_1, … , a_k, b$ of $A^n$ (for some integers $k,n>0$).
Question: Is $b$ in the subalgebra of $A^n$ generated by $a_1, … , a_k$?
In the talks I plan to survey what is currently known about this problem, emphasizing how purely algebraic results have contributed to making progress. The outline is as follows:
1. The naive algorithm; applications of more efficient algorithms.
2. An efficient algorithm for classical structures (groups, rings, modules).
3. The largest class of algebras for which a similar `generalized Gaussian elimination’ algorithm might work: forks, few subpowers, edge/parallelogram terms.
4. A sufficient condition for a finite algebra A with a parallelogram term so that there exists an efficient algorithm for SMP(A).
5. Next steps?