On effective speed-up and long proofs of trivial theorems in formal theories
Hartmanis, J.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 10 (1976), p. 29-38 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1976-01-01
@article{ITA_1976__10_1_29_0,
     author = {Hartmanis, J.},
     title = {On effective speed-up and long proofs of trivial theorems in formal theories},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {10},
     year = {1976},
     pages = {29-38},
     mrnumber = {418511},
     zbl = {0399.03042},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1976__10_1_29_0}
}

Hartmanis, J. On effective speed-up and long proofs of trivial theorems in formal theories. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 10 (1976) pp. 29-38. http://gdmltest.u-ga.fr/item/ITA_1976__10_1_29_0/

1. M. Blum. A Machine-Independent Theory of the Complexity of Recursive Function. J. Assoc. Comp. Mach., vol. 14, 1967, p. 322-336. | MR 235912 | Zbl 0155.01503

2. M. Blum and I. Marques. On Complexity Properties of Recursively Enumerable Sets. J. Symbolic Logic, vol. 38, 1973, p. 579-593. | MR 332455 | Zbl 0335.02024

3. M. J. Fischer and M. O. Rabin. Super-Exponential Complexity of Pressburger Arithmetic. In SIAM-AMS Proceedings, vol. 7, p. 27-41. American Math. Soc. Providence, RI, 1974. | MR 366646 | Zbl 0319.68024

4. J. Gill and M. Blum. On Almost Everywhere Complex Recursive Functions. J. Assoc. Comp. Mach., vol. 21, 1974, p. 425-435. | MR 457165 | Zbl 0315.68038

5. J. Hartmanis and J. E. Hopcroft. An Overview of the Theory of Computational Complexity. J. Assoc. Comp. Mach., vol. 18, 1971, p. 444-475. | MR 288028 | Zbl 0226.68024

6. N. Lynch. On Reducability to Complex or Sparse Sets. J. Assoc. Comp. Mach., vol. 22, 1975, p. 341-345. | MR 379150 | Zbl 0311.68037

7. H. Rogers. The Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967. | MR 224462 | Zbl 0183.01401

8. L. J. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic. Project MAC, Report MACTR-133, MIT, Cambridge, Mass., July 1974.