nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Introduction to Autoreducibility and Mitoticity

verfasst von : Christian Glaßer, Dung T. Nguyen, Alan L. Selman, Maximilian Witek

Erschienen in: Computability and Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We survey results on these concepts, discover surprising similarities, and, in particular explain why autoreducibility might someday separate complexity classes.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Some Questions in Computable Mathematics

Nächstes Kapitel The Complexity of Complexity

By now researchers favor the term “computably enumerable” over “recursively enumerable.” However, it is still standard that \(\mathrm {RE}\) denotes the class of c.e. sets.

[AS84]

Ambos-Spies, K.: P-mitotic sets. In: Börger, E., Hasenjaeger, G., Rödding, D. (eds.) LaM 1983. LNCS, vol. 171, pp. 1–23. Springer, Heidelberg (1984). doi:10.1007/3-540-13331-3_30 CrossRef

[Ber77]

Berman, L.: Polynomial reducibilities and complete sets. Ph.D. thesis, Cornell University, Ithaca, NY (1977)

[BF92]

Beigel, R., Feigenbaum, J.: On being incoherent without being very hard. Comput. Complex. 2, 1–17 (1992)MathSciNetCrossRefMATH

[BFvMT00]

Buhrman, H., Fortnow, L., van Melkebeek, D., Torenvliet, L.: Separating complexity classes using autoreducibility. SIAM J. Comput. 29(5), 1497–1520 (2000)MathSciNetCrossRefMATH

[BHT91]

Buhrman, H., Homer, S., Torenvliet, L.: Completeness for nondeterministic complexity classes. Math. Syst. Theory 24(3), 179–200 (1991)MathSciNetCrossRefMATH

[BT05]

Buhrman, H., Torenvliet, L.: A Post’s program for complexity theory. Bull. EATCS 85, 41–51 (2005)MathSciNetMATH

[DHGM89]

Downey, R., Homer, S., Gasarch, W., Moses, M.: On honest polynomial reductions, relativizations, and P=NP. In: IEEE Structure in Complexity Theory Conference, pp. 196–207 (1989)

[Dow85]

Downey, R.G.: The degrees of r.e. sets without the universal splitting property. Trans. Am. Math. Soc. 291(1), 337–351 (1985)MathSciNetMATH

[Dow97]

Downey, R.G.: On the universal splitting property. Math. Log. Q. 43, 311–320 (1997)MathSciNetCrossRefMATH

[DRW87]

Downey, R.G., Remmel, J.B., Welch, L.V.: Degrees of splittings and bases of recursively enumerable subspaces. Trans. Am. Math. Soc. 302(2), 683–714 (1987)MathSciNetMATH

[DS89]

Downey, R.G., Slaman, T.A.: Completely mitotic r.e. degrees. Ann. Pure Appl. Logic 41(2), 119–152 (1989)MathSciNetCrossRefMATH

[DS93a]

Downey, R.G., Stob, M.: Friedberg splittings of recursively enumerable sets. Ann. Pure Appl. Logic 59(3), 175–199 (1993)MathSciNetCrossRefMATH

[DS93b]

Downey, R.G., Stob, M.: Splitting theorems in recursion theory. Ann. Pure Appl. Logic 65(1), 1–106 (1993)MathSciNetCrossRefMATH

[DS98]

Downey, R.G., Shore, R.A.: Splitting theorems and the jump operator. Ann. Pure Appl. Logic 94(1–3), 45–52 (1998)MathSciNetCrossRefMATH

[DW86]

Downey, R.G., Welch, L.V.: Splitting properties of r. e. sets, degrees. J. Symbolic Logic 51(1), 88–109 (1986)MathSciNetCrossRefMATH

[GH92]

Ganesan, K., Homer, S.: Complete problems and strong polynomial reducibilities. SIAM J. Comput. 21, 733–742 (1992)MathSciNetCrossRefMATH

[GNR+13]

Glaßer, C., Nguyen, D.T., Reitwießner, C., Selman, A.L., Witek, M.: Autoreducibility of complete sets for log-space and polynomial-time reductions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 473–484. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39206-1_40

[GOP+07]

Glaßer, C., Ogihara, M., Pavan, A., Selman, A.L., Zhang, L.: Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. 73(5), 735–754 (2007)MathSciNetCrossRefMATH

[GPSZ08]

Glaßer, C., Pavan, A., Selman, A.L., Zhang, L.: Splitting NP-complete sets. SIAM J. Comput. 37, 1517–1535 (2008)MathSciNetCrossRefMATH

[Hom87]

Homer, S.: Minimal degrees for polynomial reducibilities. J. ACM 34(2), 480–491 (1987)MathSciNetCrossRefMATH

[Kur05]

Kurtz, S.: Private communication to Buhrman and Torenvliet [BT05] (2005)

[Lad73]

Ladner, R.: Mitotic recursively enumerable sets. J. Symbolic Logic 38(2), 199–211 (1973)MathSciNetCrossRefMATH

[Myh55]

Myhill, J.: Creative sets. Math. Logic Q. 1(2), 97–108 (1955)MathSciNetCrossRefMATH

[NS16]

Nguyen, D., Selman, A.: Structural properties of nonautoreducible sets. ACM Trans. Comput. Theory 8(3) (2016). Article No. 11

[OW91]

Ogiwara, M., Watanabe, O.: On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput. 20(3), 471–483 (1991)MathSciNetCrossRefMATH

[Tra70]

Trahtenbrot, B.: On autoreducibility. Dokl. Akad. Nauk SSSR 192, 1224–1227 (1970). (Translation in Soviet Math. Dokl. 11: 814–817 (1970))MathSciNet

[Yao90]

Yao, A.: Coherent functions and program checkers. In: Proceedings of the 22nd Annual Symposium on Theory of Computing, pp. 89–94 (1990)

Titel: Introduction to Autoreducibility and Mitoticity
verfasst von: Christian Glaßer
Dung T. Nguyen
Alan L. Selman
Maximilian Witek
Verlag: Springer International Publishing
Buch: Computability and Complexity
Print ISBN: 978-3-319-50061-4

Electronic ISBN: 978-3-319-50062-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-50062-1_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner