Fast-Growing Functions and the P vs. NP Question

Logic Journal of the IGPL 15 (5-6):445-455 (2007)
  Copy   BIBTEX

Abstract

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 exotic formalization for P=NP and then speculate about possible ways to extend our work

Categories

Keywords

Reprint years

DOI

10.1093/jigpal/jzm034

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A note on da Costa-Doria “exotic formalizations”.L. Gordeev - 2010 - Archive for Mathematical Logic 49 (7-8):813-821.
Theory of Fuzzy Time Computation (2, P vs NP problem).Didehvar Farzad - manuscript
TC+CON(TC*) deduce P is not equal to NP.Didehvar Farzad - manuscript
Theory of Fuzzy Time Computation (2) (TC+CON(〖TC*〗)ͰP≠NP).Didehvar Farzad - manuscript
Consequences of the Provability of NP ⊆ P/poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
P^f NP^f for almost all f.J. D. Hamkins - 2003 - Mathematical Logic Quarterly 49 (5):536.
Consequences of an Exotic Definition for P = NP. Applied Mathematics and Computation.N. C. A. da Costa & F. A. Doria - 2004 - Bulletin of Symbolic Logic 10 (1):118-119.
P f≠ NP f for almost all f.Joel David Hamkins & Philip D. Welch - 2003 - Mathematical Logic Quarterly 49 (5):536-540.
A Class of Examples Demonstrating That 'P ≠ NP' in the 'P Vs NP' Problem.Vasil Penchev - 2020 - Computing Methodology eJournal (Elsevier: SSRN) 3 (19):1-19.

Analytics

Added to PP
2015-02-04

Downloads
15 (#1,236,051)

6 months
6 (#866,322)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references