[33] Show that for all t ≥ 2, the set C[tlog n, nt

, ∞] is Pisomorphic to {0}∗.

Comments. Source: [E. Allender and O. Watanabe, Inform. Comput., 86

(1990), 160–178]. In this paper, the authors also use sets C[tlog n, nt

, ∞]

to study the equivalent classes of tally sets under various types of reductions. Compare with [S. Tang and R.V. Book, Theoret. Comput.

Sci., 81:1(1991), 35–47; R. Gavald`a and O. Watanabe, SIAM J. Comput., 22(6) (1993), 1257–1275; H. Buhrman, E. Hemaspaandra, and L.

Longpr´e, SIAM J. Comput., 24:4(1995), 673–681].