A recursion-theoretic characterisation of the positive polynomial-time functions
From MaRDI portal
Publication:5079742
DOI10.4230/LIPIcs.CSL.2018.18OpenAlexW2889165966MaRDI QIDQ5079742
Publication date: 28 May 2022
Full work available at URL: https://doi.org/10.4230/lipics.csl.2018.18
logicfunction algebrasimplicit complexitymonotone complexityfunction classespositive complexityrecursion-theoretic characterisations
Related Items
Cites Work
- The monotone circuit complexity of Boolean functions
- On uniform circuit complexity
- A new recursion-theoretic characterization of the polytime functions
- Complete sets and the polynomial-time hierarchy
- Positive versions of polynomial time
- A foundational delineation of poly-time
- The gap between monotone and non-monotone circuit complexity is exponential
- On uniformity within \(NC^ 1\)
- Classes of Predictably Computable Functions
- From positive and intuitionistic bounded arithmetic to monotone proof complexity
- Monotone Boolean functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item