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.
Get full access to this article
View all access options for this article.