首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:A Survey of Classes of Primitive Recursive Functions
  • 本地全文:下载
  • 作者:Stephen A. Cook
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    This paper is a transcription of mimeographed course notes titled ``A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function classes (and classes of relations based on these classes,) including Cobham's class \L of polynomial time functions, and Bennett's class (denoted here by \L + ) of extended positive rudimentary functions. It is noted that \L + corresponds to those functions computable in nondeterministic polynomial time and that \L \L + , and it is conjectured that this inclusion is proper. Relational versions of these classes are also introduced, and a similar inclusion is noted. This is likely the earliest consideration in print of the relationship between the complexity classes P and NP, in both functional and relational forms.

    The numbering of sections and theorems corresponds to that in the original notes. However, page numbering does not correspond to the page numbering of the original. Minor typographical errors have been corrected.

国家哲学社会科学文献中心版权所有