Skip Navigation


Logic Journal of IGPL Advance Access originally published online on September 24, 2007
Logic Journal of IGPL 2007 15(5-6):445-455; doi:10.1093/jigpal/jzm034
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Doria, F. A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2007. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Fast-Growing Functions and the P vs. NP Question

Francisco Antonio Doria

Fuzzy Sets Research Team, PIT, Production Engineering Program. Room F108, COPPE, UFRJ, P.O. Box 68507, 21945–972 Rio RJ Brazil. E-mail: fadoria{at}pep.ufrj.br

Out of a folklore–like fact about the counterexample function to P=NP, a function which grows about as fast as the Busy Beaver function, we review the consequences of our (with da Costa) exotic formalization for P=NP and then speculate about possible ways to extend our work.

Key Words: computational complexity • fast-growing functions • Busy Beaver function • P vs. NP

Received for publication 24 October 2006. Revision received .

References

  1. Baker T, Gill J, Solovay R. ‘Relativizations of the P=?NP question," SIAM J. Comp. (1975) 4:431–442.[CrossRef]

  2. Beklemishev L. ‘Provability and reflection," In: Lecture Notes for ESSLLI'97 (1997).

  3. Ben-David S, Halevi S. ‘On the independence of P , vs. NP. In: Technical Report # 699 (1991) Technion.

  4. da Costa NCA, Doria FA. ‘Consequences of an exotic formulation for P=NP," . Applied Mathematics and Computation (2003) 145:655–665. also ‘Addendum," Applied Mathematics and Computation 172, 1364–1367 (2006).[CrossRef][ISI]

  5. da Costa NCA, Doria FA. ‘Computing the future," In: Computability, Complexity and Constructivity in Economic Analysis—Vela Velupillai K, ed. (2005) Blackwell.

  6. da Costa NCA, Doria FA. ‘Paradoxical arguments and the P vs. NP question,"to appear. (2007).

  7. da Costa NCA, Doria FA. ‘Some folklore about the P vs. NP question," to appear. (2007).

  8. Doria FA. ‘Informal vs. formal mathematics," . Synthèse (2007) 154:401–415.[CrossRef][ISI]

  9. Feferman S. ‘Transfinite recursive progressions of axiomatic theories," . J. Symbolic Logic (1962) 27:259–316.[CrossRef]

  10. Fortune S, Leivant D, O'Donnell M. ‘The expressiveness of simple and second–order type structures," . J. ACM (1983) 38:151–185.

  11. Franzen T. ‘Transfinite progressions: a second look at completeness," Bull. Symbolic Logic (2004) 10:367–389.[CrossRef]

  12. Gödel K. ‘Undecidable Diophantine propositions [193?]," Collected Works III (1995).

  13. Gödel K. ‘Some basic theorems on the foundations of mathematics and their implications [1951]," Collected Works III (1995).

  14. Guillaume M. e–mail messages to the authors, 2000–2003.

  15. Guillaume M. ‘What counts in an exotic formulation...," (2003) unpublished draft.

  16. Kaye R. Models of Peano Arithmetic (1991) Clarendon Press.

  17. Kleene SC. ‘General recursive functions of natural numbers," Math. Ann. (1936) 112:727.[CrossRef]

  18. Kleene SC. Mathematical Logic (1967) Wiley.

  19. Koellner P. ‘On the question of absolute undecidability," In: Philosophia Mathematica III (2006) 14:153–188.[CrossRef]

  20. Kreisel G. ‘On the interpretation of non–finitist proofs," I, J. Symbol. Logic (1951) 16:241. II, 17, 43 (1952).[CrossRef]

  21. Shapiro S. ‘Incompleteness, mechanism and optimism," . Bull. Symbolic Logic (1998) 4:273–302.[CrossRef]

  22. Smorynski C. Logical Number Theory, I (1991) Springer.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Doria, F. A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?