
University of Bonn > Department of Computer Science > Chair V  
CSReports 2008  Copyright 2008 University of Bonn, Department of Computer Science, Abt. V  
85300 17.12.2008 
Scaled Dimension and the BermanHartmanis Conjecture
Mathias Hauptmann [Download PostScript] [Download PDF] In 1977, L. Berman and J. Hartmanis [BH77] conjectured that all polynomialtime manyone complete sets for NP are are pairwise polynomially isomorphic. It was stated as an open problem in [LM99] to resolve this conjecture under the measure hypothesis from quantitative complexity theory. In this paper we study the polynomialtime isomorphism degrees within deg_{m}^{p}(SAT) in the context of polynomial scaled dimension. Our results are the following:


Last Change:
12/18/08 at 14:00:28
Deutsch 
University of Bonn > Department of Computer Science > Chair V 