and Petri net reachability, thus showing they are computationally infeasible for large instances.

The inverse of the Ackermann function appears in some time complexity results. For instance, the disjoint-set data structure takes amortized time per operation proportional to the inverse Ackermann function, and cannot be made faster within the cell-probe model of