View in EDS PDF Full Text

Forcing with Random Variables and Proof Complexity

Saved in:
Bibliographic Details
Title: Forcing with Random Variables and Proof Complexity
Description: 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.
Authors: Jan Krajíček
Resource Type: eBook.
Subjects: Mathematical analysis, Computational complexity, Random variables
Categories: MATHEMATICS / Infinity, MATHEMATICS / Logic
Database: eBook Collection (EBSCOhost)
FullText Links:
  – Type: ebook-pdf
Text:
  Availability: 0
Header DbId: nlebk
DbLabel: eBook Collection (EBSCOhost)
An: 399278
RelevancyScore: 1038
AccessLevel: 6
PubType: eBook
PubTypeId: ebook
PreciseRelevancyScore: 1037.72192382813
IllustrationInfo
ImageInfo – Size: thumb
  Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$399278$PDF&s=r
– Size: medium
  Target: https://rps2images.ebscohost.com/rpsweb/othumb?id=NL$399278$PDF&s=d
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Forcing with Random Variables and Proof Complexity
– Name: Abstract
  Label: Description
  Group: Ab
  Data: 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.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Jan+Krajíček%22">Jan Krajíček</searchLink>
– Name: TypePub
  Label: Resource Type
  Group: TypPub
  Data: eBook.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Mathematical+analysis%22">Mathematical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Random+variables%22">Random variables</searchLink>
– Name: SubjectBISAC
  Label: Categories
  Group: Su
  Data: <searchLink fieldCode="ZK" term="%22MATHEMATICS+%2F+Infinity%22">MATHEMATICS / Infinity</searchLink><br /><searchLink fieldCode="ZK" term="%22MATHEMATICS+%2F+Logic%22">MATHEMATICS / Logic</searchLink>
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=399278
RecordInfo BibRecord:
  BibEntity:
    Classifications:
      – Code: 511.36
        Scheme: ddc
        Type: prePub
    Languages:
      – Code: eng
        Text: English
    Subjects:
      – SubjectFull: Mathematical analysis
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Random variables
        Type: general
    Titles:
      – TitleFull: Forcing with Random Variables and Proof Complexity
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Jan Krajíček
      – PersonEntity:
          Name:
            NameFull: Jan Krajíček
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Type: published
              Y: 2011
            – D: 04
              M: 02
              Type: profile
              Y: 2014
          Identifiers:
            – Type: isbn-print
              Value: 9780521154338
            – Type: isbn-electronic
              Value: 9781139127998
          Numbering:
            – Type: volume
              Value: 00382
          Titles:
            – TitleFull: Forcing with Random Variables and Proof Complexity
              Type: main
ResultId 1