Skip to main content

Arithmetic theories for computational complexity problems

Publication ,  Journal Article
Homer, S; Reif, J
Published in: Information and Control
January 1, 1986

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.

Duke Scholars

Published In

Information and Control

DOI

ISSN

0019-9958

Publication Date

January 1, 1986

Volume

69

Issue

1-3

Start / End Page

1 / 11
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Homer, S., & Reif, J. (1986). Arithmetic theories for computational complexity problems. Information and Control, 69(1–3), 1–11. https://doi.org/10.1016/S0019-9958(86)80041-9
Homer, S., and J. Reif. “Arithmetic theories for computational complexity problems.” Information and Control 69, no. 1–3 (January 1, 1986): 1–11. https://doi.org/10.1016/S0019-9958(86)80041-9.
Homer S, Reif J. Arithmetic theories for computational complexity problems. Information and Control. 1986 Jan 1;69(1–3):1–11.
Homer, S., and J. Reif. “Arithmetic theories for computational complexity problems.” Information and Control, vol. 69, no. 1–3, Jan. 1986, pp. 1–11. Scopus, doi:10.1016/S0019-9958(86)80041-9.
Homer S, Reif J. Arithmetic theories for computational complexity problems. Information and Control. 1986 Jan 1;69(1–3):1–11.

Published In

Information and Control

DOI

ISSN

0019-9958

Publication Date

January 1, 1986

Volume

69

Issue

1-3

Start / End Page

1 / 11