
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2008  Copyright 2008 Universität Bonn, Institut für Informatik, 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 