A Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmetic¹

Article type: Research Article

Authors: Deborah, Joseph | Young, Paul

Affiliations: University of Wisconsin, University of Washington

Note: [1] This paper is a revised version of a paper presented at the 10th Symposium on the Mathematical Foundations of Computer Science, Strbske Pleso, Czechoslovakia (August 31 – September 4, 1981).

Abstract: In spite of the fact that much effort has been expended trying to prove lower bounds for algorithms and trying to solve the P = NP question, only limited progress has been made. Although most computer scientists remain convinced that solutions will be found, others (Hartmanis and Hopcroft, Fortune, Leivant and O’Donnell, and Phillips) have questioned the adequacy of Peano arithmetic for computer science. This uncertainty has only been increased by the recent work of Paris and Harrington showing that certain simple, finitistic, combinatorial statements are in fact independent of Peano Arithmetic. In this paper we survey complexity theoretic statements that are known to be independent of arithmetic theories. In addition we survey recent results analyzing the arithmetic quantifier structure of computational problems.

Keywords: Independence results, NP = ? coNP, P = ? NP, Peano arithmetic

DOI: 10.3233/FI-1985-8109

Journal: Fundamenta Informaticae, vol. 8, no. 1, pp. 103-121, 1985