JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Importance of Being II2-Hard

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-01Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-961
Type
technical report