×

Bounded recursively enumerable sets and degrees. (English) Zbl 0807.03027

Summary: A new reducibility between recursive sets is defined, which is appropriate to be used in the study of the polynomial reducibility and the NP-problem.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jense, D., and Ehrenfeucht, A., Some problems in elementary arithmetic.Fundamenta Mathematicae, 1976, 92, 223–245. · Zbl 0362.02049
[2] McAloon, K., On the complexity of models of arithmetic.J. Symbolic Logic, 1982, 47, 403–415. · Zbl 0519.03056 · doi:10.2307/2273150
[3] Paris, J., and Wilkie, A., {\(\Delta\)}0- sets and induction.Open Days in Model Theory and Set Theory (Proceedings of the Jadwish Conference, 1981; W. Guzickiet al., editors).
[4] Soare, R. I., Recursively Enumerable Sets and Degrees, an study of computable functions and computably generated sets. {\(\omega\)} series, Springer-Verlag, 1987. · Zbl 0667.03030
[5] Wilmers, G., Bounded existential induction.J. Symbolic Logic, 1985, 50, 72–90. · Zbl 0634.03029 · doi:10.2307/2273790
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.