Strong polynomial-time reducibility

Annals of Pure and Applied Logic 84 (1):97-117 (1997)

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(96)00037-1
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 48,902
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
On MODkP Counting Degrees.Masamitsu Ozaki & Juichi Shinoda - 1999 - Mathematical Logic Quarterly 45 (3):327-342.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
Polynomial Clone Reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.


Added to PP index

Total views
10 ( #790,521 of 2,309,951 )

Recent downloads (6 months)
2 ( #521,891 of 2,309,951 )

How can I increase my downloads?


My notes

Sign in to use this feature