On the Importance of Being II2-Hard

Abstract

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.