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