Complexity of Boolean Functions - Wegener_ Ingo.pdf - Complexity of Boolean Functions (1165) - superktos86

The

Complexity of

Boolean

Functions

Ingo Wegener

Johann Wolfgang Goethe-Universitat

WARNING:

This version of the book is for your personal use only. The material

is copyrighted and may not be redistributed.

No part of this book may be reproduced by any means, or transmitted, or translated

into a machine language without the written permission of the publisher.

Library of Congress Cataloguing in Publication Data:

Wegener, Ingo

The complexity of boolean functions.

(Wiley-Teubner series in computer science)

Bibliography: p.

Includes index.

1. Algebra, Boolean. 2. Computational complexity.

I. Title. II. Series.

AQ10.3.W44 1987 511.3’24 87-10388

ISBN 0 471 91555 6 (Wiley)

British Library Cataloguing in Publication Data:

Wegener, Ingo

The complexity of Boolean functions.—(Wiley-Teubner series in computer science).

1. Electronic data processing—Mathematics 2. Algebra, Boolean

I. Title. II. Teubner, B. G.

004.01’511324

QA76.9.M3

ISBN 0 471 91555 6

CIP-Kurztitelaufnahme der Deutschen Bibliothek

Wegener, Ingo

The complexity of Boolean functions/Ingo Wegener.—Stuttgart: Teubner; Chich-

ester; New York; Brisbane; Toronto; Singapore: Wiley, 1987

(Wiley-Teubner series in computer science)

ISBN 3 519 02107 2 (Teubner)

ISBN 0 471 91555 6 (Wiley)

Printed and bound in Great Britain

On this version of the “Blue Book”

This version of “The Complexity of Boolean Functions,” for some

people simply the “Blue Book” due to the color of the cover of the orig-

inal from 1987, is not a print-out of the original sources. It is rather a

“facsimile” of the original monograph typeset in L A T E X.

The source les of the Blue Book which still exist (in 1999) have been

written for an old version of troff and virtually cannot be printed out

anymore. This is because the (strange) standard font used for the text

as well as the special fonts for math symbols seem to be nowhere to

nd today. Even if one could nd a solution for the special symbols, the

available text fonts yield a considerably dierent page layout which seems

to be undesirable. Things are further complicated by the fact that the

source les for the gures have been lost and would have to be redone

with pic .

Hence, it has been decided to translate the whole sources to L A T E X

in order to be able to x the above problems more easily. Of course,

the result can still only be an approximation to the original. The fonts

are those of the CM series of A T E X and have dierent parameters than

the original ones. For the spacing of equations, the standard mechanisms

of A T E X have been used, which are quite dierent from those of troff .

Hence, it is nearly unavoidable that page breaks occur at dierent places

than in the original book. Nevertheless, it has been made sure that all

numbered items (theorems, equations) can be found on the same pages

as in the original.

You are encouraged to report typos and other errors to Ingo Wegener

by e-mail: wegener@ls2.cs.uni-dortmund.de

Preface

When Goethe had fundamentally rewritten his IPHIGENIE AUF

TAURIS eight years after its rst publication, he stated (with resig-

nation, or perhaps as an excuse or just an explanation) that, ˝Such a

work is never actually nished: one has to declare it nished when one

has done all that time and circumstances will allow.˝ This is also my

feeling after working on a book in a eld of science which is so much

in ux as the complexity of Boolean functions. On the one hand it is

time to set down in a monograph the multiplicity of important new

results; on the other hand new results are constantly being added.

I have tried to describe the latest state of research concerning re-

sults and methods. Apart from the classical circuit model and the

parameters of complexity, circuit size and depth, providing the basis

for sequential and for parallel computations, numerous other models

have been analysed, among them monotone circuits, Boolean formu-

las, synchronous circuits, probabilistic circuits, programmable (univer-

sal) circuits, bounded depth circuits, parallel random access machines

and branching programs. Relationships between various parameters of

complexity and various models are studied, and also the relationships

to the theory of complexity and uniform computation models.

The book may be used as the basis for lectures and, due to the

inclusion of a multitude of new ndings, also for seminar purposes.

Numerous exercises provide the opportunity of practising the acquired

methods. The book is essentially complete in itself, requiring only

basic knowledge of computer science and mathematics.

This book I feel should not just be read with interest but should

encourage the reader to do further research. I do hope, therefore, to

have written a book in accordance with Voltaire’s statement, ˝The

most useful books are those that make the reader want to add to

Complexity of Boolean Functions - Wegener_ Ingo.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: