On the Importance of Being II2-Hard
Permanent Link(s)
Collections
Author
Hartmanis, Juris
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.
Date Issued
1989-01
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-961
Type
technical report