000			02315cam a22003494a 4500
001			16429416
003			OSt
005			20150408114018.0
008			100823s2011 enka b 001 0 eng
010			_a 2010036194
020			_a9780521154338
020			_a0521154332 (pbk.)
035			_a(OCoLC)ocn664450704
040			_aDLC _cDLC _dYDX _dYDXCP _dIXA _dCDX _dBWX _dDLC
042			_apcc
050	0	0	_aQA267.7 _b.K73 2011
082	0	0	_a511.36 _222
100	1		_aKrajíček, Jan _914355
245	1	0	_aForcing with random variables and proof complexity / _cJan Krajíček.
260			_aCambridge, UK ; _aNew York : _bCambridge University Press, _c2011.
300			_axvi, 247 p. : _bill. ; _c23 cm.
490	1		_aLondon Mathematical Society lecture note series ; _v382
504			_aIncludes bibliographical references (p. 236-242) and indexes.
520			_a"This book introduces a new approach to building models of bounded arithmetic, with techniques drawn from recent results in computational complexity. Propositional proof systems and bounded arithmetics are closely related. In particular, proving lower bounds on the lengths of proofs in propositional proof systems is equivalent to constructing certain extensions of models of bounded arithmetic. This offers a clean and coherent framework for thinking about lower bounds for proof lengths, and it has proved quite successful in the past. This book outlines a brand new method for constructing models of bounded arithmetic, thus for proving independence results and establishing lower bounds for proof lengths. The models are built from random variables defined on a sample space which is a non-standard finite set and sampled by functions of some restricted computational complexity. It will appeal to anyone interested in logical approaches to fundamental problems in complexity theory"--
650		0	_aComputational complexity.
650		0	_aRandom variables. _914356
650		0	_aMathematical analysis. _94615
830		0	_aLondon Mathematical Society lecture note series ; _v382. _914357
856	4	2	_3Cover image _uhttp://assets.cambridge.org/97805211/54338/cover/9780521154338.jpg
942			_2ddc _cBOOK
999			_c21732 _d256232