@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 = {Revue fran\c{c}aise d'automatique informatique recherche op\'erationnelle. Informatique th\'eorique}, pages = {29--38}, publisher = {Dunod-Gauthier-Villars}, address = {Paris}, volume = {10}, number = {R1}, year = {1976}, mrnumber = {418511}, zbl = {0399.03042}, language = {en}, url = {http://www.numdam.org/item/ITA_1976__10_1_29_0/} }
TY - JOUR AU - Hartmanis, J. TI - On effective speed-up and long proofs of trivial theorems in formal theories JO - Revue française d'automatique informatique recherche opérationnelle. Informatique théorique PY - 1976 SP - 29 EP - 38 VL - 10 IS - R1 PB - Dunod-Gauthier-Villars PP - Paris UR - http://www.numdam.org/item/ITA_1976__10_1_29_0/ LA - en ID - ITA_1976__10_1_29_0 ER -
%0 Journal Article %A Hartmanis, J. %T On effective speed-up and long proofs of trivial theorems in formal theories %J Revue française d'automatique informatique recherche opérationnelle. Informatique théorique %D 1976 %P 29-38 %V 10 %N R1 %I Dunod-Gauthier-Villars %C Paris %U http://www.numdam.org/item/ITA_1976__10_1_29_0/ %G en %F ITA_1976__10_1_29_0
Hartmanis, J. On effective speed-up and long proofs of trivial theorems in formal theories. Revue française d'automatique informatique recherche opérationnelle. Informatique théorique, Tome 10 (1976) no. R1, pp. 29-38. http://www.numdam.org/item/ITA_1976__10_1_29_0/
1. A Machine-Independent Theory of the Complexity of Recursive Function. J. Assoc. Comp. Mach., vol. 14, 1967, p. 322-336. | MR | Zbl
.2. On Complexity Properties of Recursively Enumerable Sets. J. Symbolic Logic, vol. 38, 1973, p. 579-593. | MR | Zbl
and .3. Super-Exponential Complexity of Pressburger Arithmetic. In SIAM-AMS Proceedings, vol. 7, p. 27-41. American Math. Soc. Providence, RI, 1974. | MR | Zbl
and .4. On Almost Everywhere Complex Recursive Functions. J. Assoc. Comp. Mach., vol. 21, 1974, p. 425-435. | MR | Zbl
and .5. An Overview of the Theory of Computational Complexity. J. Assoc. Comp. Mach., vol. 18, 1971, p. 444-475. | MR | Zbl
and .6. On Reducability to Complex or Sparse Sets. J. Assoc. Comp. Mach., vol. 22, 1975, p. 341-345. | MR | Zbl
.7. The Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967. | MR | Zbl
.8. The Complexity of Decision Problems in Automata Theory and Logic. Project MAC, Report MACTR-133, MIT, Cambridge, Mass., July 1974.
,