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

DOI10.4230/LIPICS.CSL.2018.18OpenAlexW2889165966MaRDI QIDQ5079742FDOQ5079742

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)

Cites Work

• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• A new recursion-theoretic characterization of the polytime functions
• Monotone Boolean functions
• The monotone circuit complexity of Boolean functions
• Complete sets and the polynomial-time hierarchy
• The gap between monotone and non-monotone circuit complexity is exponential
• A foundational delineation of poly-time
• Classes of Predictably Computable Functions
• Positive versions of polynomial time
• From positive and intuitionistic bounded arithmetic to monotone proof complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

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