Functions and Polynomials over Finite Groups from the Computational Perspective

Abstract

In the thesis we investigate the connections between arbitrary functions and their realizing polynomials over finite algebras. We study functionally complete algebras, i.e. algebras over which every function can be realized by a polynomial expression. We characterize functional completeness by the so called Stone-Weierstrass property, and we determine the functionally complete semigroups and semirings. Then we investigate the computational perspective of the function-polynomial relationships over finite groups. We consider the efficient representability, the equivalence, and the equation solvability problems.

We approach the efficient representability problem from three directions. We consider the length of functions, we investigate the circuit complexity of functions, and we analyse the finite-state sequential machine representation of Boolean functions. From each of these viewpoints we give bounds on the potential efficiency of computations based on functionally complete groups compared to computations based on the two-element Boolean algebra.

Neither the equivalence problem nor the equation solvability problem has been completely characterized for finite groups. The complexity of the equivalence problem was only known for nilpotent groups. In the thesis we determine the complexity of the equivalence problem for certain meta-Abelian groups and for all non-solvable groups.

The complexity of the equation solvability problem is known for nilpotent groups and for non-solvable groups. There are no results about the complexity of the equation solvability problem for solvable non-nilpotent groups apart from the case of certain meta-cyclic groups that we present in the thesis. Moreover, we determine the complexity of the equation solvability problem for all functionally complete algebra.

The idea of the extended equivalence problem emerges from the observation that the commutator might significantly change the length of group-polynomials. We characterize the complexity of the extended equivalence problem for finite groups. For many finite groups we determine the complexity of the equivalence problem if the commutator is considered as the basic operation of the group.