The Resource Bounded arithmetic, propositional logic, and complexity theory, Jan Krajicek

Bounded arithmetic, propositional logic, and complexity theory, Jan Krajicek

Label
Bounded arithmetic, propositional logic, and complexity theory
Title
Bounded arithmetic, propositional logic, and complexity theory
Statement of responsibility
Jan Krajicek
Title variation
Bounded Arithmetic, Propositional Logic & Complexity Theory
Creator
Author
Subject
Language
eng
Summary
This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are then treated, including polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area
Member of
Cataloging source
UkCbUP
http://library.link/vocab/creatorName
Krajíček, Jan
Dewey number
511.3
Index
index present
LC call number
QA9.56
LC item number
.K73 1995
Literary form
non fiction
Nature of contents
dictionaries
Series statement
Encyclopedia of mathematics and its applications
Series volume
volume 60
http://library.link/vocab/subjectName
  • Constructive mathematics
  • Proposition (Logic)
  • Computational complexity
Label
Bounded arithmetic, propositional logic, and complexity theory, Jan Krajicek
Link
https://doi.org/10.1017/CBO9780511529948
Instantiates
Publication
Note
Title from publisher's bibliographic system (viewed on 05 Oct 2015)
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Extent
1 online resource (xiv, 343 pages)
Form of item
online
Isbn
9780511529948
Isbn Type
(ebook)
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
digital, PDF file(s).
Specific material designation
remote
System control number
(UkCbUP)CR9780511529948
Label
Bounded arithmetic, propositional logic, and complexity theory, Jan Krajicek
Link
https://doi.org/10.1017/CBO9780511529948
Publication
Note
Title from publisher's bibliographic system (viewed on 05 Oct 2015)
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Extent
1 online resource (xiv, 343 pages)
Form of item
online
Isbn
9780511529948
Isbn Type
(ebook)
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other physical details
digital, PDF file(s).
Specific material designation
remote
System control number
(UkCbUP)CR9780511529948

Library Locations

  • Architecture LibraryBorrow it
    Gould Hall 830 Van Vleet Oval Rm. 105, Norman, OK, 73019, US
    35.205706 -97.445050
  • Bizzell Memorial LibraryBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Boorstin CollectionBorrow it
    401 W. Brooks St., Norman, OK, 73019, US
    35.207487 -97.447906
  • Chinese Literature Translation ArchiveBorrow it
    401 W. Brooks St., RM 414, Norman, OK, 73019, US
    35.207487 -97.447906
  • Engineering LibraryBorrow it
    Felgar Hall 865 Asp Avenue, Rm. 222, Norman, OK, 73019, US
    35.205706 -97.445050
  • Fine Arts LibraryBorrow it
    Catlett Music Center 500 West Boyd Street, Rm. 20, Norman, OK, 73019, US
    35.210371 -97.448244
  • Harry W. Bass Business History CollectionBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • History of Science CollectionsBorrow it
    401 W. Brooks St., Rm. 521NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • John and Mary Nichols Rare Books and Special CollectionsBorrow it
    401 W. Brooks St., Rm. 509NW, Norman, OK, 73019, US
    35.207487 -97.447906
  • Library Service CenterBorrow it
    2601 Technology Place, Norman, OK, 73019, US
    35.185561 -97.398361
  • Price College Digital LibraryBorrow it
    Adams Hall 102 307 West Brooks St., Norman, OK, 73019, US
    35.210371 -97.448244
  • Western History CollectionsBorrow it
    Monnet Hall 630 Parrington Oval, Rm. 300, Norman, OK, 73019, US
    35.209584 -97.445414
Processing Feedback ...