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

DOI10.4230/LIPICS.CSL.2018.18MaRDI QIDQ5079742zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A new recursion-theoretic characterization of the polytime functions
• Function algebraic characterizations of the polytime functions
• A new function algebra of EXPTIME functions by safe nested recursion
• Safe Weak Minimization Revisited
• Monotonicity constraints in characterizations of PSPACE

Cites work

• scientific article; zbMATH DE number 1670877 (Why is no real title available?)
• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• scientific article; zbMATH DE number 1018349 (Why is no real title available?)
• scientific article; zbMATH DE number 953683 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• A foundational delineation of poly-time
• A new recursion-theoretic characterization of the polytime functions
• Classes of Predictably Computable Functions
• Complete sets and the polynomial-time hierarchy
• From positive and intuitionistic bounded arithmetic to monotone proof complexity
• Logical foundations of proof complexity
• Monotone Boolean functions
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Positive versions of polynomial time
• The gap between monotone and non-monotone circuit complexity is exponential
• The monotone circuit complexity of Boolean functions

Cited in

(2)

• Proof complexity of positive branching programs
• Proof complexity of monotone branching programs

This page was built for publication: A recursion-theoretic characterisation of the positive polynomial-time functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5079742)