This book principally concerns the rapidly growing area of what might be termed "Logical Complexity Theory": the study of bounded arithmetic, propositional proof systems, length of proof, and similar themes, and the relations of these topics to computational complexity theory. Issuing from a two-year international collaboration, the book contains articles concerning the existence of the most general unifier, a special case of Kreisel's conjecture on length-of-proof, propositional logic proof size, a new alternating logtime algorithm for boolean formula evaluation and relation to branching...

Recently molecular biology has undergone unprecedented development generating vast quantities of data needing sophisticated computational methods for analysis, processing and archiving. This requirement has given birth to the truly interdisciplinary field of computational biology, or bioinformatics, a subject reliant on both theoretical and practical contributions from statistics, mathematics, computer science and biology.

* Provides the background mathematics required to understand why certain algorithms work
* Guides the reader through probability theory, entropy and...

Recently molecular biology has undergone unprecedented development generating vast quantities of data needing sophisticated computational methods for analysis, processing and archiving. This requirement has given birth to the truly interdisciplinary field of computational biology, or bioinformatics, a subject reliant on both theoretical and practical contributions from statistics, mathematics, computer science and biology.

* Provides the background mathematics required to understand why certain algorithms work
* Guides the reader through probability theory, entropy and...

The foundations of computational complexity theory go back to Alan Thring in the 1930s who was concerned with the existence of automatic procedures deciding the validity of mathematical statements. The first example of such a problem was the undecidability of the Halting Problem which is essentially the question of debugging a computer program: Will a given program eventu- ally halt? Computational complexity today addresses the quantitative aspects of the solutions obtained: Is the problem to be solved tractable? But how does one measure the intractability of computation? Several ideas were...

The foundations of computational complexity theory go back to Alan Thring in the 1930s who was concerned with the existence of automatic procedures deciding the validity of mathematical statements. The first example of such a problem was the undecidability of the Halting Problem which is essentially the question of debugging a computer program: Will a given program eventu- ally halt? Computational complexity today addresses the quantitative aspects of the solutions obtained: Is the problem to be solved tractable? But how does one measure the intractability of computation? Several ideas were...

Perspicuity is part of proof. If the process by means of which I get a result were not surveyable, I might indeed make a note that this number is what comes out - but what fact is this supposed to confirm for me? I don't know 'what is supposed to come out' . . . . 1 -L. Wittgenstein A feasible computation uses small resources on an abstract computa- tion device, such as a 'lUring machine or boolean circuit. Feasible math- ematics concerns the study of feasible computations, using combinatorics and logic, as well as the study of feasibly presented mathematical structures such as groups,...