Proof complexity and feasible arithmetics : DIMACS workshop, April 21-24, 1996
著者
書誌事項
Proof complexity and feasible arithmetics : DIMACS workshop, April 21-24, 1996
（DIMACS series in discrete mathematics and theoretical computer science, v. 39）
American Mathematical Society, c1998
大学図書館所蔵 件 / 全22件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Papers from the proceedings of a workshop held in Rutgers, N.J
Includes bibliographical references
内容説明・目次
内容説明
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.
目次
Plausibly hard combinatorial tautologies by J. Avigad More on the relative strength of counting principles by P. Beame and S. Riis Ranking arithmetic proofs by implicit ramification by S. J. Bellantoni Lower bounds on Nullstellensatz proofs via designs by S. R. Buss Relating the provable collapse of $\mathbfP$ to $\mathrm {NC}^1$ and the power of logical theories by S. Cook On $PHP$, $st$-connectivity, and odd charged graphs by P. Clote and A. Setzer Descriptive complexity and the $W$ hierarchy by R. G. Downey, M. R. Fellows, and K. W. Regan Lower bounds on the sizes of cutting plane proofs for modular coloring principles by X. Fu Equational calculi and constant depth propositional proofs by J. Johannsen Exponential lower bounds for semantic resolution by S. Jukna Bounded arithmetic: Comparison of Buss' witnessing method and Sieg's Herbrand analysis by B. Kauffmann Towards lower bounds for bounded-depth Frege proofs with modular connectives by A. Maciel and T. Pitassi A quantifier-free theory based on a string algebra for $NC^1$ by F. Pitt A propositional proof system for $R^i_2$ by C. Pollett Algebraic models of computation and interpolation for algebraic proof systems by P. Pudlak and J. Sgall Self-reflection principles and NP-hardness by D. E. Willard.
「Nielsen BookData」 より