文档介绍：Texts in puter Science
An EATCS Series
Editors: W. Brauer G. Rozenberg A. Salomaa
On behalf of the European Association
for puter Science (EATCS)
Advisory Board: G. Ausiello M. Broy . Calude
A. Condon D. Harel J. Hartmanis T. Henzinger
J. Hromkovic° N. Jones T. Leighton M. Nivat
C. Papadimitriou D. Scott
Jörg Rothe
Complexity Theory
and Cryptology
An Introduction to plexity
With 63 Figures and 56 Tables
123
Author
Prof. Dr. Jörg Rothe
Universität Düsseldorf
Institut für Informatik
Universitätsstr. 1
40225 Düsseldorf, Germany
******@-
Series Editors
Prof. Dr. Wilfried Brauer
Institut für Informatik der TUM
Boltzmannstrasse 3
85748 Garching, Germany
******@-
Prof. Dr. Grzegorz Rozenberg
Leiden Institute of puter Science
University of Leiden
Niels Bohrweg 1
2333 CA Leiden, herlands
******@
Prof. Dr. Arto Salomaa
Turku Centre puter Science
Lemminkäisenkatu 14 A
20520 Turku, Finland
******@
Library of Congress Control Number: 2005928704
puting Classification (1998): , F. ,
ISBN-10 3-540-22147-6 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-22147-0 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned,
specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm
or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under
the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must
always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
© Springer-Verlag Berlin Heidelberg 2005
Printed in Germany
The use of general descriptive names, registered names, trademarks,