Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Proof Complexity and Feasible Arithmetics
 
Edited by: Paul W. Beame University of Washington, Seattle, WA
Samuel R. Buss University of California at San Diego, La Jolla, CA
A co-publication of the AMS and DIMACS
Proof Complexity and Feasible Arithmetics
Hardcover ISBN:  978-0-8218-0577-0
Product Code:  DIMACS/39
List Price: $84.00
MAA Member Price: $75.60
AMS Member Price: $67.20
eBook ISBN:  978-1-4704-3997-2
Product Code:  DIMACS/39.E
List Price: $79.00
MAA Member Price: $71.10
AMS Member Price: $63.20
Hardcover ISBN:  978-0-8218-0577-0
eBook: ISBN:  978-1-4704-3997-2
Product Code:  DIMACS/39.B
List Price: $163.00 $123.50
MAA Member Price: $146.70 $111.15
AMS Member Price: $130.40 $98.80
Proof Complexity and Feasible Arithmetics
Click above image for expanded view
Proof Complexity and Feasible Arithmetics
Edited by: Paul W. Beame University of Washington, Seattle, WA
Samuel R. Buss University of California at San Diego, La Jolla, CA
A co-publication of the AMS and DIMACS
Hardcover ISBN:  978-0-8218-0577-0
Product Code:  DIMACS/39
List Price: $84.00
MAA Member Price: $75.60
AMS Member Price: $67.20
eBook ISBN:  978-1-4704-3997-2
Product Code:  DIMACS/39.E
List Price: $79.00
MAA Member Price: $71.10
AMS Member Price: $63.20
Hardcover ISBN:  978-0-8218-0577-0
eBook ISBN:  978-1-4704-3997-2
Product Code:  DIMACS/39.B
List Price: $163.00 $123.50
MAA Member Price: $146.70 $111.15
AMS Member Price: $130.40 $98.80
  • Book Details
     
     
    DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
    Volume: 391998; 320 pp
    MSC: Primary 03; 68;

    Questions of mathematical proof and logical inference have been a significant thread in modern mathematics and have played a formative role in the development of computer science and artificial intelligence. Research in proof complexity and feasible theories of arithmetic aims at understanding not only whether logical inferences can be made, but also what resources are required to carry them out. Understanding the resources required for logical inferences has major implications for some of the most important problems in computational complexity, particularly the problem of whether NP is equal to co-NP. In addition, these have important implications for the efficiency of automated reasoning systems.

    The last dozen years have seen several breakthroughs in the study of these resource requirements. Papers in this volume represent the proceedings of the DIMACS workshop on “Feasible Arithmetics and Proof Complexity” held in April 1996 at Rutgers University in New Jersey as part of the DIMACS Institute's Special Year on Logic and Algorithms.

    This book brings together some of the most recent work of leading researchers in proof complexity and feasible arithmetic reflecting many of these advances. It covers a number of aspects of the field, including lower bounds in proof complexity, witnessing theorems and proof systems for feasible arithmetic, algebraic and combinatorial proof systems, interpolation theorems, and the relationship between proof complexity and Boolean circuit complexity.

    Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

    Readership

    Graduate students and research mathematicians interested in mathematical logic and foundations.

  • Table of Contents
     
     
    • Chapters
    • Plausibly hard combinatorial tautologies
    • More on the relative strength of counting principles
    • Ranking arithmetic proofs by implicit ramification
    • Lower bounds on Nullstellensatz proofs via designs
    • Relating the provable collapse of $\mathbf P$ to ${\mathbf NC}^1$ and the power of logical theories
    • On $PHP$, $st$-connectivity, and odd charged graphs
    • Descriptive complexity and the $W$ hierarchy
    • Lower bounds on sizes of cutting plane proofs for modular coloring principles
    • Equational calculi and constant depth propositional proofs
    • Exponential lower bounds for semantic resolution
    • Bounded arithmetic: Comparison of Buss’ witnessing method and Sieg’s Herbrand analysis
    • Towards lower bounds for bounded-depth Frege proofs with modular connectives
    • A quantifier-free theory based on a string algebra for $NC^1$
    • A propositional proof system for $R^i_2$
    • Algebraic models of computation and interpolation for algebraic proof systems
    • Self-reflection principles and NP-hardness
  • Reviews
     
     
    • The volume adequately reflects current interests and trends in the area of feasible proofs, and many papers in it simply define the current state of the art there. Its importance for everybody interested in this beautiful theory, be it the experienced researcher, a beginner, or just a curious outsider, can hardly be overstated.

      Journal of Symbolic Logic
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 391998; 320 pp
MSC: Primary 03; 68;

Questions of mathematical proof and logical inference have been a significant thread in modern mathematics and have played a formative role in the development of computer science and artificial intelligence. Research in proof complexity and feasible theories of arithmetic aims at understanding not only whether logical inferences can be made, but also what resources are required to carry them out. Understanding the resources required for logical inferences has major implications for some of the most important problems in computational complexity, particularly the problem of whether NP is equal to co-NP. In addition, these have important implications for the efficiency of automated reasoning systems.

The last dozen years have seen several breakthroughs in the study of these resource requirements. Papers in this volume represent the proceedings of the DIMACS workshop on “Feasible Arithmetics and Proof Complexity” held in April 1996 at Rutgers University in New Jersey as part of the DIMACS Institute's Special Year on Logic and Algorithms.

This book brings together some of the most recent work of leading researchers in proof complexity and feasible arithmetic reflecting many of these advances. It covers a number of aspects of the field, including lower bounds in proof complexity, witnessing theorems and proof systems for feasible arithmetic, algebraic and combinatorial proof systems, interpolation theorems, and the relationship between proof complexity and Boolean circuit complexity.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

Readership

Graduate students and research mathematicians interested in mathematical logic and foundations.

  • Chapters
  • Plausibly hard combinatorial tautologies
  • More on the relative strength of counting principles
  • Ranking arithmetic proofs by implicit ramification
  • Lower bounds on Nullstellensatz proofs via designs
  • Relating the provable collapse of $\mathbf P$ to ${\mathbf NC}^1$ and the power of logical theories
  • On $PHP$, $st$-connectivity, and odd charged graphs
  • Descriptive complexity and the $W$ hierarchy
  • Lower bounds on sizes of cutting plane proofs for modular coloring principles
  • Equational calculi and constant depth propositional proofs
  • Exponential lower bounds for semantic resolution
  • Bounded arithmetic: Comparison of Buss’ witnessing method and Sieg’s Herbrand analysis
  • Towards lower bounds for bounded-depth Frege proofs with modular connectives
  • A quantifier-free theory based on a string algebra for $NC^1$
  • A propositional proof system for $R^i_2$
  • Algebraic models of computation and interpolation for algebraic proof systems
  • Self-reflection principles and NP-hardness
  • The volume adequately reflects current interests and trends in the area of feasible proofs, and many papers in it simply define the current state of the art there. Its importance for everybody interested in this beautiful theory, be it the experienced researcher, a beginner, or just a curious outsider, can hardly be overstated.

    Journal of Symbolic Logic
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.