# On effective speed-up and long proofs of trivial theorems in formal theories

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1976)

- Volume: 10, Issue: R1, page 29-38
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topHartmanis, J.. "On effective speed-up and long proofs of trivial theorems in formal theories." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 10.R1 (1976): 29-38. <http://eudml.org/doc/92026>.

@article{Hartmanis1976,

author = {Hartmanis, J.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {Speed-Up; Decidable; Axiomatizable; Formal Theories; Theorem Proving; Complexity of Proofs; Algorithm},

language = {eng},

number = {R1},

pages = {29-38},

publisher = {EDP-Sciences},

title = {On effective speed-up and long proofs of trivial theorems in formal theories},

url = {http://eudml.org/doc/92026},

volume = {10},

year = {1976},

}

TY - JOUR

AU - Hartmanis, J.

TI - On effective speed-up and long proofs of trivial theorems in formal theories

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 1976

PB - EDP-Sciences

VL - 10

IS - R1

SP - 29

EP - 38

LA - eng

KW - Speed-Up; Decidable; Axiomatizable; Formal Theories; Theorem Proving; Complexity of Proofs; Algorithm

UR - http://eudml.org/doc/92026

ER -

## References

top- 1. M. BLUM. A Machine-Independent Theory of the Complexity of Recursive Function. J. Assoc. Comp. Mach., vol. 14, 1967, p. 322-336. Zbl0155.01503MR235912
- 2. M. BLUM and I. MARQUES. On Complexity Properties of Recursively Enumerable Sets. J. Symbolic Logic, vol. 38, 1973, p. 579-593. Zbl0335.02024MR332455
- 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. Zbl0319.68024MR366646
- 4. J. GILL and M. BLUM. On Almost Everywhere Complex Recursive Functions. J. Assoc. Comp. Mach., vol. 21, 1974, p. 425-435. Zbl0315.68038MR457165
- 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. Zbl0226.68024MR288028
- 6. N. LYNCH. On Reducability to Complex or Sparse Sets. J. Assoc. Comp. Mach., vol. 22, 1975, p. 341-345. Zbl0311.68037MR379150
- 7. H. ROGERS. The Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967. Zbl0183.01401MR224462
- 8. L. J. STOCKMEYER, The Complexity of Decision Problems in Automata Theory and Logic. Project MAC, Report MACTR-133, MIT, Cambridge, Mass., July 1974.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.