Completeness Classes in Algebra
Leslie Gabriel Valiant · ACM eBooks · 1979
In the theory of recursive functions and computational complexity it has been demonstrated repeatedly that the natural problems tend to cluster together in “completeness classes”. These are families of problems that (A) are computationally interreducible and (B) are the hardest members of some computationally defined class. The aim of this paper is to demonstrate that for both algebraic and combinatorial problems this phenomenon exists in a form that is purely algebraic in both of the respects (A) and (B). Such computational consequences as NP-completeness are particular manifestations of something more fundamental.