Show simple item record

dc.contributor.authorJoseph, Deborah A.en_US
dc.contributor.authorYoung, P. R.en_US
dc.description.abstractIn 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.en_US
dc.format.extent1782844 bytes
dc.format.extent477573 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleA Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmeticen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record