Boolean functions and computation models

Peter Clote, Evangelos Kranakis

612 pages, parution le 16/10/2002

Ajouter à une liste

Indisponible

Résumé

This advanced textbook is a survey of the present state of research in the study of boolean functions, formulas, circuits, propositional proof systems, and models of computation. All of these subjects are related to the overriding concern of how computation can be modeled, and what limitations and interrelations there are between different computation models.Starting with methods for the construction of boolean circuits which compute certain arithmetic and combinatorial functions, upper and lower bounds for circuit families are investigated. The techniques used are from combinatorics, probability and finite group theory. Then a survey is given on steps taken in a program initiated by S.A. Cook for investigating non-deterministic polynomial time, from a proof-theoretic viewpoint. Specifically, lower bounds are presented for lengths of proofs for families of prepositional tautologies, when proven in certain proof systems. Techniques here involve both logic and finite combinatorics and are related to constant-depth boolean circuits and to monotone arithmetic circuits.Numerous exercises at the end of each chapter enhance understanding of the material and expand research topics covered. Thus, the book will benefit advanced undergraduate and graduate students as well as researchers in the field of complexity theory. Contents

Boolean Functions and Circuits
Circuit Lower Bounds
Circuit Upper Bounds
Randomness and Satisfiability
Propositional Proof Systems
Machine Models and Function Algebras
Higher Types

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Peter Clote, Evangelos Kranakis
Parution	16/10/2002
Nb. de pages	612
Format	16 x 24
Couverture	Relié
Poids	1068g
Intérieur	Noir et Blanc
EAN13	9783540594369