In spite of the fact that a great deal of 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, finistic, 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.