Evaluation of permanents in rings and semirings

A study was conducted to present simple folklore algorithms to evaluate the permanent of a given matrix. Bellman-Held-Karp type dynamic programming was applied across column subsets in arbitrary semirings and showed that a transposed variant was considerably faster in commutative semirings. The starting point in arbitrary rings was Ryser's classic algorithm that was managed to expedite for rectangular matrices, remaining as the fastest known algorithm for square matrices. The time requirement of an algorithm was taken as the number of additions and multiplications it performed, to state the complexity bounds for each of the four cases. The space requirement was taken as the maximum number of semiring elements needed to keep in memory at any point in the computation. The study also discussed the role of commutativity where the first theorem suggested that commutativity was crucial for efficient evaluation of permanents.