Publications [#237101] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Homer, S; Reif, J, Arithmetic theories for computational complexity problems, Information and Control, vol. 69 no. 1-3 (January, 1986), pp. 1-11, Elsevier BV, ISSN 0019-9958 [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper considers a number of arithmetic theories and shows how the strength of these theories relates to certain open problems in complexity theory concerning the polynomial-time hierarchy. These results are proved quite generally and hold for a wide class of subrecursive hierarchies. They can be used to characterize certain properties of functions provable in these theories. © 1986 Academic Press, Inc.