On the Importance of Being II 2 -Hard.
Juris Hartmanis · eCommons (Cornell University) · 1989
In this column, we show how a variety of interesting results in theory of computation all follow from a simple observation about $\prod _{2}$-complete sets of total machines. We easily derive: a) representation independent independence results, b) non-recursive succinctness relations between different representations of languages, c) the existence of incomplete languages in various complexity classes.