Logic Journal of IGPL

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 Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by Doria, F. A. Search for Related Content Social Bookmarking          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][Web of Science]

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][Web of Science]

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  Smornski C. Logical Number Theory, I (1991) Springer.

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

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