Abstract
Many computational complexity problems, including constraint satisfaction and weighted counting constraint satisfaction problems, graph isomorphism, and others, can be expressed in a unified way as word problems in certain kinds of monoidal categories over finite tensor signatures. Using categories axiomitizes notions such as planarity and avoids long combinatorial descriptions, as well as characterizing the difference between problems. It allows the tools of category theory to be brought to bear on complexity problems and allows reductions to be expressed as functors. This approach also generates many new open problems as we vary the kind of monoidal category, the representation functor, and the tensor signature.