國立虎尾科技大學 |

登入

回首頁

Forcing with random variables and pr...

Krajíček, Jan

Forcing with random variables and proof complexity /

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Forcing with random variables and proof complexity // Jan Krajíček.
作者:	Krajíček, Jan
出版者:	Cambridge, UK ;Cambridge University Press, : 2011.,
面頁冊數:	xvi, 247 p. ;23 cm.;
標題:	Mathematical analysis. -
電子資源:	http://assets.cambridge.org/97805211/54338/cover/9780521154338.jpg
ISBN:	9780521154338 (pbk.) :

Forcing with random variables and proof complexity /
Krajíček, Jan

Forcing with random variables and proof complexity /Jan Krajíček. - Cambridge, UK ;Cambridge University Press,2011. - xvi, 247 p. ;23 cm. - London Mathematical Society lecture note series ;382. - London Mathematical Society lecture note series ;382..

Includes bibliographical references (p. 236-242) and indexes.

"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"--

ISBN: 9780521154338 (pbk.) :NT1880

LCCN: 2010036194Subjects--Topical Terms:

527926
Mathematical analysis.

LC Class. No.: QA267.7 / .K73 2011

Dewey Class. No.: 511.3/6

Forcing with random variables and proof complexity /
LDR:01896cam a2200253 a 4500 001 671356
005 20110629163415.0
008 110706s2011 enk b 001 0 eng
010 $a 2010036194
020 $a 9780521154338 (pbk.) : $c NT1880
020 $a 0521154332 (pbk.)
035 $a (OCoLC)ocn664450704
035 $a 2010036194
040 $a DLC $c DLC $d YDX $d YDXCP $d IXA $d CDX $d BWX $d DLC
041 0 # $a eng
042 $a pcc
050 0 0 $a QA267.7 $b .K73 2011
082 0 0 $a 511.3/6 $2 22
100 1 $a Krajíček, Jan $3 773476
245 1 0 $a Forcing with random variables and proof complexity / $c Jan Krajíček.
260 # $a Cambridge, UK ; $a New York : $c 2011. $b Cambridge University Press,
300 $a xvi, 247 p. ; $c 23 cm.
490 1 $a London Mathematical Society lecture note series ; $v 382
504 $a Includes 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"-- $c Provided by publisher.
650 # 0 $a Mathematical analysis. $3 527926
650 # 0 $a Random variables. $3 598296
650 # 0 $a Computational complexity. $3 527777
830 0 $a London Mathematical Society lecture note series ; $v 382. $3 773477
856 4 2 $3 Cover image $u http://assets.cambridge.org/97805211/54338/cover/9780521154338.jpg