Mardigian Library
Ask a QuestionMy Library Account
Search Library Catalog - Books, DVDs & More
Limit to available
More Searches
   
Limit results to available items
Find more results:
Search MelCat
More Information
  
Krajíček, Jan
Forcing with random variables and proof complexity / Jan Krajíček
Cambridge, UK ; New York : Cambridge University Press, c2011
book jacket
Location Call Number Status
 4th Floor  QA267.7 .K73 2011    AVAILABLE
Subject(s) Computational complexity
Random variables
Mathematical analysis
Physical Description xvi, 247 p. : ill. ; 23 cm
Note Includes bibliographical references (p. 236-242) and indexes
Summary "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"-- Provided by publisher
Series London Mathematical Society lecture note series ; 382

Mardigian Library, 4901 Evergreen Rd.
Dearborn, MI 48128-1491 313-593-5400 fax 313-593-5561
ask-a-question@umd.umich.edu
The Regents of the University of Michigan | Non-Discrimination Policy
Copyright © The University of Michigan - Dearborn • 4901 Evergreen Road • Dearborn, Michigan 48128 • 313-593-5000
The University of Michigan - Ann Arbor | The University of Michigan - Flint | SITEMAP | DIRECTORY | CONTACT