Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2008 Copyright 2008 University of Bonn, Department of Computer Science, Abt. V


Scaled Dimension and the Berman-Hartmanis Conjecture
Mathias Hauptmann
[Download PostScript] [Download PDF]

In 1977, L. Berman and J. Hartmanis [BH77] conjectured that all polynomial-time many-one 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 polynomial-time isomorphism degrees within degmp(SAT) in the context of polynomial scaled dimension. Our results are the following:

  1. We consider scaled dimensions of order in between -2 and -3. Especially we define scaled dimensions dimp(-2,k), kN.
  2. Let ISOmp(SAT) denote the polynomial-time isomorphism degree of SAT. While for each k, dimp(-2,k)(degmp(SAT)) = dimp(-2,k)(NP), if r is a growth rate function of order smaller than every order (-2,k), then dimp(r)(ISOmp(SAT)) = 0.
  3. We consider the class of disjoint unions L1L2 of NP-complete languages L1, L2 such that L1 and L2 are polynomially isomorphic. We show that for |i | ≤ 2 the i-th order scaled dimension of this class equals that of NP. The same holds for the scaled dimensions dimp(-2,k).
Last Change: 12/18/08 at 14:00:28
University of Bonn -> Department of Computer Science -> Chair V