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.
An Isaac Newton Institute ProgrammeLogic and AlgorithmsForcing with random variables and complexity of computations and proofs20th April 2006 Author: Krajicek, J (Prague) AbstractWe 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. |