Fast-Growing Functions and the P vs. NP Question

DOI10.1093/JIGPAL/JZM034MaRDI QIDQ5436986zbMATH OpenOpenAlexFDO

Authors Francisco Antonio Doria

Publication date 18 January 2008

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/jigpal/jzm034

zbMATH Keywords

busy beaver functioncomputational complexityfast-growing functionsP-NP problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A note on da Costa-Doria ``exotic formalizations
• Consequences of an exotic definition for \(\text{P}=\text{NP}\).
• On the P vs NP question: a proof of inequality
• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
• \(\mathrm P \overset {?} {=} \mathrm{NP}\)

Cited in

(3)

• On the P vs NP question: a proof of inequality
• A note on da Costa-Doria ``exotic formalizations
• Kolmogorov complexity and degrees of tally sets

This page was built for publication: Fast-Growing Functions and the P vs. NP Question

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