Strong polynomial-time reducibility

https://doi.org/10.1016/S0168-0072(96)00037-1Get rights and content
Under an Elsevier user license
open archive

Abstract

The degree structure of functions induced by a polynomial-time reducibility first introduced in G. Miller's work on the complexity of prime factorization is investigated. Several basic results are established including the facts that the degrees restricted to the sets do not form an upper semilattice and there is a minimal degree, as well as density for the low degrees, a weak form of the exact pair theorem, the existence of minimal pairs and the decidability of the Π2 theory of the low degrees.

MSC

68Q15
03D15
03D30

Keywords

Computational complexity
Polynomial-time reducibilities
Polynomial-time degrees

Cited by (0)