Document Open Access Logo

A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions

Authors Anupam Das, Isabel Oitavem

PDF

File

Thumbnail PDF
PDF
LIPIcs.CSL.2018.18.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Recursive functions
Keywords
  • Monotone complexity
  • Positive complexity
  • Function classes
  • Function algebras
  • Recursion-theoretic characterisations
  • Implicit complexity
  • Logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We extend work of Lautemann, Schwentick and Stewart [Clemens Lautemann et al., 1996] on characterisations of the "positive" polynomial-time predicates (posP, also called mP by Grigni and Sipser [Grigni and Sipser, 1992]) to function classes. Our main result is the obtention of a function algebra for the positive polynomial-time functions (posFP) by imposing a simple uniformity constraint on the bounded recursion operator in Cobham's characterisation of FP. We show that a similar constraint on a function algebra based on safe recursion, in the style of Bellantoni and Cook [Stephen Bellantoni and Stephen A. Cook, 1992], yields an "implicit" characterisation of posFP, mentioning neither explicit bounds nor explicit monotonicity constraints.

Cite As Get BibTex

Anupam Das and Isabel Oitavem. A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CSL.2018.18

Author Details

Anupam Das
  • University of Copenhagen, Denmark
Isabel Oitavem
  • CMA and DM, FCT, Universidade Nova de Lisboa, Portugal

Funding

  • Das, Anupam: This work was supported by a Marie Skłodowska-Curie fellowship, Monotonicity in Logic and Complexity, ERC project 753431.
  • Oitavem, Isabel: This work is partially supported by the Portuguese Science Foundation, FCT, through the projects UID/MAT/00297/2013 and PTDC/MHC-FIL/2583/2014.

References

  1. Noga Alon and Ravi B Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1-22, 1987. Google Scholar
  2. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On Uniformity within NC¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. URL: http://dx.doi.org/10.1016/0022-0000(90)90022-D.
  3. Stephen Bellantoni and Stephen A. Cook. A new recursion-theoretic characterization of the polytime functions. Computational Complexity, 2:97-110, 1992. URL: http://dx.doi.org/10.1007/BF01201998.
  4. Samuel R. Buss. Bounded arithmetic, volume 1 of Studies in Proof Theory. Bibliopolis, Naples, 1986. Google Scholar
  5. Peter Clote and Evangelos Kranakis. Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002. URL: http://dx.doi.org/10.1007/978-3-662-04943-3.
  6. A. Cobham. The intrinsic computational difficulty of functions. In Proc. of the International Congress for Logic, Methodology, and the Philosophy of Science, pages 24-30. Amsterdam, 1965. Google Scholar
  7. Stephen Cook and Phuong Nguyen. Logical Foundations of Proof Complexity. Cambridge University Press, New York, NY, USA, 1st edition, 2010. Google Scholar
  8. Anupam Das. From positive and intuitionistic bounded arithmetic to monotone proof complexity. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 126-135, 2016. URL: http://dx.doi.org/10.1145/2933575.2934570.
  9. Fernando Ferreira. Polynomial time computable arithmetic. In Contemporary Mathematics, volume 106, pages 137-156. AMS, 1990. Google Scholar
  10. Michelangelo Grigni. Structure in monotone complexity. PhD thesis, Duke University, 1991. Google Scholar
  11. Michelangelo Grigni and Michael Sipser. Monotone complexity. In London Mathematical Society Symposium on Boolean Function Complexity, New York, NY, USA, 1992. Cambridge University Press. Google Scholar
  12. Andrzej Grzegorczyk. Some classes of recursive functions. Instytut Matematyczny Polskiej Akademi Nauk, 1953. Google Scholar
  13. A D Korshunov. Monotone boolean functions. Russian Mathematical Surveys, 58(5), 2003. Google Scholar
  14. Clemens Lautemann, Thomas Schwentick, and Iain A. Stewart. On positive P. In IEEE Conference on Computational Complexity '96, 1996. Google Scholar
  15. Clemens Lautemann, Thomas Schwentick, and Iain A. Stewart. Positive versions of polynomial time. Inf. Comput., 147(2):145-170, 1998. URL: http://dx.doi.org/10.1006/inco.1998.2742.
  16. Daniel Leivant. A foundational delineation of computational feasiblity. In Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS '91), Amsterdam, The Netherlands, July 15-18, 1991, pages 2-11, 1991. URL: http://dx.doi.org/10.1109/LICS.1991.151625.
  17. Daniel Leivant. A foundational delineation of poly-time. Inf. Comput., 110(2):391-420, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1038.
  18. Isabel Oitavem. New recursive characterizations of the elementary functions and the functions computable in polynomial space. Revista Matematica de la Universidad Complutense de Madrid, 10(1):109-125, 1997. Google Scholar
  19. Christos H. Papadimitriou. Computational complexity. Academic Internet Publ., 2007. Google Scholar
  20. A. A. Razborov. Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR, 285, 1985. Google Scholar
  21. Robert W. Ritchie. Classes of predictably computable functions. Journal of Symbolic Logic, 28(3):252-253, 1963. Google Scholar
  22. Walter L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22(3):365-383, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90038-6.
  23. E. Tardos. The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141-142, 1988. Google Scholar
  24. Celia Wrathall. Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci., 3(1):23-33, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90062-1.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact