A New Gap Theorem: the Gap Theorem’s Robustness Against Dominance
Ed Blakey
Thanks to Trachtenbrot and Borodin, complexity theorists have the Gap Theorem, which guarantees the existence of arbitrarily large gaps in the complexity hierarchy. That is, there can be made arbitrarily large increases in resource availability that, for all their vastness, yield no additional computational power: every computation that can be performed given the extra resource could have been performed in its absence.
In response to needs arising during the complexity analysis of unconventional— quantum, analogue, chemical, optical, etc.—computers, the notion of dominance was introduced (we recap in the present paper the relevant definitions). With dominance comes a corresponding hierarchy of complexity classes, and it is natural to ask whether a gap theorem, analogous to that of Trachtenbrot and Borodin, holds in this context.
We show that a gap theorem does indeed hold for certain dominance-based classes. We consider related statements concerning other dominance-based classes, and formulate corresponding conjectures.
Keywords: Gap Theorem, Dominance, Computational Complexity, Computability, Comparison of Complexity, Unconventional Computing