Editing Ackermann function (section)

=== In computational complexity ===

The Ackermann function appears in the time [[computational complexity theory|complexity]] of some [[algorithm]]s,{{sfn|Brubaker|2023}} such as [[vector addition system]]s{{sfn|Czerwiński|Orlikowski|2022}} and [[Reachability_problem#Petri_nets|Petri net reachability]], thus showing they are computationally infeasible for large instances.{{sfn|Leroux|2022}}

The [[#Inverse|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,{{sfn|Tarjan|1975}} and cannot be made faster within the [[cell-probe model]] of computational complexity.{{sfn|Fredman|Saks|1989}}