Forcing with Random Variables and Proof Complexity
A model-theoretic approach to bounded arithmetic and propositional proof complexity.
Read More ↓Title Statements
- Full title :Forcing with Random Variables and Proof Complexity.
Summary
A model-theoretic approach to bounded arithmetic and propositional proof complexity.
Read More ↓Edition Statements
- Publication Date:2010.
Publication Statements
- Publisher(s):Cambridge University Press
- Place of Publication:Cambridge
- Language:eng
- Publication Date:2010.
Notes
19 PHP principle.
The Physical Object
- Description:1 online resource (266 pages)
Edition Identifiers
- ISBN:9781139117333, 1139117335, 9781139127998, 1139127993, 9781139115162, 1139115162, 9781139107211, 1139107216
- oclc:ocn769341802
- LC Classification:QA267.7 .K73 2011
- Dewey Decimal:511.36
Table of Contents
Cover; Title; Copyright; Dedication; Contents; Preface; Acknowledgment; Introduction; Organization of the book; Remarks on the literature; Background; Part I Basics; 1 The definition of the models; 1.1 The ambient model of arithmetic; 1.2 The Boolean algebras; 1.3 The models K(F); 1.4 Valid sentences; 1.5 Possible generalizations; 2 Measure on B; 2.1 A metric on B; 2.2 From Boolean value to probability; 3 Witnessing quantifiers; 3.1 Propositional approximation of truth values; 3.2 Witnessing in definable families; 3.3 Definition by cases by open formulas; 3.4 Compact families.
3.5 Propositional computation of truth values4 The truth in N and the validity in K(F); Part II Second-order structures; 5 Structures K(F, G); 5.1 Language L2 and the hierarchy of bounded formulas; 5.2 Cut Mn, languages Ln and L2n; 5.3 Definition of the structures; 5.4 Equality of functions, extensionality and possible generalizations; 5.5 Absoluteness of ASb8-sentences of language Ln; Part III AC0 world; 6 Theories I?0, I?0(R) and V01; 7 Shallow Boolean decision tree model; 7.1 Family Frud; 7.2 Family Grud; 7.3 Properties of Frud and Grud; 8 Open comprehension and open induction.
8.1 The ((. . .)) notatio…
Rate & Review