Arithmetic theories for computational complexity problems


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Homer, S; Reif, J

Published Date

  • January 1, 1986

Published In

Volume / Issue

  • 69 / 1-3

Start / End Page

  • 1 - 11

International Standard Serial Number (ISSN)

  • 0019-9958

Digital Object Identifier (DOI)

  • 10.1016/S0019-9958(86)80041-9

Citation Source

  • Scopus