Title :
Bounded arithmetic and computational complexity
Author_Institution :
Dept. of Comput. Sci., Boston Coll., Chestnut Hill, MA, USA
Abstract :
A survey of certain characterizations of complexity classes in an algebraic, machine-independent manner is presented, together with some applications to weak theories of arithmetic and higher-order functionals. Function algebras are examined, and hierarchies are defined. Bounded arithmetic theories are presented
Keywords :
computational complexity; bounded arithmetic; complexity classes; computational complexity; function algebras; higher-order functionals; Algebra; Application software; Arithmetic; Computational complexity; Computer science; Educational institutions; Formal languages; Logic functions; Logic programming; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113967
