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
Fast-Growing Functions and the P vs. NP Question
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]
| ||||||||||||||||||||||||||||||||||||||||||||||||
nski C. Logical Number Theory, I (1991) Springer.