On MODkP Counting Degrees

Mathematical Logic Quarterly 45 (3):327-342 (1999)

For a prime k, the embeddability of finite lattices are discussed for various kind of the MODkP degrees of recursive sets. In particular, all finite lattices are embeddable into the MODkP Turing degrees, whereas the non distributive lattice M3 is embeddable into the MOD2P many-one degrees but N5 is not
Keywords Nondeterministic Computation  Counting reducibility  Polynomial time reducibility
Categories (categorize this paper)
DOI 10.1002/malq.19990450305
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: 47,413
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.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
Strong Polynomial-Time Reducibility.Juichi Shinoda - 1997 - Annals of Pure and Applied Logic 84 (1):97-117.
On the Reducibility of Relations: Variations on a Theme of Peirce.Ernst Kleinert - 2007 - Transactions of the Charles S. Peirce Society 43 (3):509 - 520.
Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
A New Reducibility Between Turing‐ and Wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
Wtt-Degrees and T-Degrees of R.E. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Approximate Counting by Hashing in Bounded Arithmetic.Emil Jeřábek - 2009 - Journal of Symbolic Logic 74 (3):829-860.
Polynomial Clone Reducibility.Quinn Culver - 2014 - Archive for Mathematical Logic 53 (1-2):1-10.
1-Reducibility Inside an M-Degree with Maximal Set.E. Herrmann - 1992 - Journal of Symbolic Logic 57 (3):1046-1056.


Added to PP index

Total views
6 ( #1,006,524 of 2,291,824 )

Recent downloads (6 months)
2 ( #575,103 of 2,291,824 )

How can I increase my downloads?


My notes

Sign in to use this feature