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

J. Hartmanis

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

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

How to cite

top

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 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. 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. 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. 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. 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. 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. 6. N. LYNCH. On Reducability to Complex or Sparse Sets. J. Assoc. Comp. Mach., vol. 22, 1975, p. 341-345. Zbl0311.68037MR379150
  7. 7. H. ROGERS. The Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967. Zbl0183.01401MR224462
  8. 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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.