九大理学部 3 号館 (箱崎) Room 3109, Faculty of Science, Kyushu University (Hakozaki).
Abstract
In the intersection of abstract algebra and computer science,
computational group theory is a research area concerning methods of
computation, both theoretical and practical, in groups. Over the last
several decades, this subject has experienced a period of vigorous
development. As a result, in practice, group-theoretic software
systems have successfully served mathematicians and scientists as key
tools for many important discoveries.
Although there are numerous instances of applications, an important
motivation for our research is relationship with the graph-isomorphism
problem: given two graphs, test whether or not they are isomorphic.
The problem is of fundamental importance in the theory of computing
because of its as yet unresolved membership status in the complexity
classes P and NP-complete.
This talk will highlight some of my research in computational group
theory, with a focus on problems that resemble or generalize the
graph-isomorphism problem. I will summarize instances where the
problems are known to be solvable in polynomial time and indicate
methods that enable such efficiency.
http://www.math.kobe-u.ac.jp/seminars.html