The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

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.