A recursion-theoretic characterisation of the positive polynomial-time functions

DOI10.4230/LIPIcs.CSL.2018.18OpenAlexW2889165966MaRDI QIDQ5079742

Anupam Das, Isabel Oitavem

Publication date: 28 May 2022

Full work available at URL: https://doi.org/10.4230/lipics.csl.2018.18

zbMATH Keywords

logicfunction algebrasimplicit complexitymonotone complexityfunction classespositive complexityrecursion-theoretic characterisations

Mathematics Subject Classification ID

Logic in computer science (03B70)

Related Items

Proof complexity of monotone branching programs

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