Abstract: This aims to clearly define a group-theoretical problem that could prove intractable for artificial intelligence systems under reasonable computational assumptions. Specifically, we first establish a class of problems that are well-specified algorithmically and can be explicitly solved for small instances. However, their complexity increases exponentially with the size of the permutation groups involved. We strongly believe that an instance of a known intractable problem can be embedded into this class, leading to intractability for any AI system as well. Here, we will outline the foundation of this idea and present several implementation examples using Mathematica and GAP. The second goal of this work is to introduce a new method for assessing the reasoning abilities of AI systems. Instead of relying on the traditional "if from–> into then from–> what?" matrix configurations used in earlier IQ tests like Raven’s, our approach provides a much deeper perspective. While it maintains a solid mathematical foundation, it is interactive, scalable, abstract, capable of displaying limitless complexity, and involves significantly less mimicry or template-based learning. Additionally, it emphasizes the self-discovered, creative aspects of intelligent behavior. Throughout the development of this work, several Computer Algebra Systems were used extensively or occasionally.

Keywords: Groups, Permutation groups, Action of a group on a set, Orbits, Artificial Intelligence, Tests for reasoning capability of AI systems

Pages: 189-200