The problem of deciding whether two universal relational sentences have the same spectrum is solvable by an algorithm whose run time is bounded by a linear stack of 2s, but not by an algorithm whose run time is bounded by a fixed stack of 2s. © 1984 Academic Press, Inc.
