Geometry and complexity of O'Hara's algorithm

[摘要] In this paper we analyze O;;Hara;;s partition bijection. We present three type of results. First, we show that O;;Hara;;s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O;;Hara;;s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O;;Hara;;s bijection can be computed in polynomial time, i.e. much more efficiently than by O;;Hara;;s construction.

[发布机构] Elsevier