EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A recursion-theoretic characterization of monotone NP

Isabel Oitavem, Eduardo Skapinakis

Archive for Mathematical Logic · 05.11.2026

DOI: 10.1007/s00153-026-01040-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Archive for Mathematical Logic, online erschienen am 05.11.2026. Verfasst von Isabel Oitavem und 1 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundação para a Ciência e a Tecnologia.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper we give a recursion-theoretic characterization and a new machine model for the complexity class , the class of functions which are monotone. This is the first recursion-theoretic approach to a monotone/positive class of non-deterministic nature. The recursion scheme developed here has the potential to be applied to other monotone/positive classes based on non-deterministic models of computation. Moreover, the recursion-theoretic approach introduced in this work leads to a new machine model for $$\texttt {mNP}$$ mNP of remarkable simplicity.

Förderung

  • Fundação para a Ciência e a Tecnologia

Zitieren

APA

Oitavem, I., & Skapinakis, E. (2026). A recursion-theoretic characterization of monotone NP. Archive for Mathematical Logic. https://doi.org/10.1007/s00153-026-01040-4

Vancouver

Oitavem I, Skapinakis E. A recursion-theoretic characterization of monotone NP. Archive for Mathematical Logic. 2026. doi:10.1007/s00153-026-01040-4

BibTeX
@article{Oitavem2026,
  author = {Oitavem, Isabel and Skapinakis, Eduardo},
  title = {A recursion-theoretic characterization of monotone NP},
  journal = {Archive for Mathematical Logic},
  year = {2026},
  doi = {10.1007/s00153-026-01040-4}
}
Kostenlos starten →