An Isaac Newton Institute Programme

Logic and Algorithms

Forcing with random variables and complexity of computations and proofs

20th April 2006

Author: Krajicek, J (Prague)

Abstract

We develop a new construction of models of arithmetic. The models are Boolean-valued and are based on random variables. We outline some applications to bounded arithmetic and to complexity theory.