17.12.2008

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 deg_m^p(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 dim_p^(-2,k), k ∈N.
2. Let ISO_m^p(SAT) denote the polynomial-time isomorphism degree of SAT. While for each k, dim_p^(-2,k)(deg_m^p(SAT)) = dim_p^(-2,k)(NP), if r is a growth rate function of order smaller than every order (-2,k), then dim_p^(r)(ISO_m^p(SAT)) = 0.
3. We consider the class of disjoint unions L₁ ⊕ L₂ of NP-complete languages L₁, L₂ such that L₁ and L₂ 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 dim_p^(-2,k).