Selected publications at LSV

Abstract:
We introduce a hierarchy of fast-growing complexity classes and show its suitability for completeness statements of many non elementary problems. This hierarchy allows the classification of many decision problems with a non-elementary complexity, which occur naturally in logic, combinatorics, formal languages, verification, etc., with complexities ranging from simple towers of exponentials to Ackermannian and beyond.

@article{toct-Schmitz13,
   author = {Schmitz, Sylvain},
   DOI = {10.1145/2858784},
   journal = {ACM Transactions on Computation Theory},
   month = feb,
   number = {1:3},
   publisher = {ACM Press},
   title = {Complexity Hierarchies Beyond {E}lementary},
   url = {http://arxiv.org/abs/1312.5686},
   volume = {8},
   year = {2016},
}

About LSV

Select by Year