Algebraic Complexity Theory With the Collaboration of Thomas Licktei
The algorithmic solution of problems has always been one of the major concerns of mathematics. For a long time such solutions were based on an intuitive notion of algorithm. It is only in this century that metamathematical problems have led to the intensi
- PDF / 52,638,004 Bytes
- 630 Pages / 439.37 x 666.14 pts Page_size
- 38 Downloads / 148 Views
..
...
... &
T·
..
A Series of Comprehensive Studies in Mathematics
Editors
S. S. Chern B. Eckmann P. de la Harpe H. Hironaka F. Hirzebruch N. Hitchin 1. Hormander M.-A. Knus A. Kupiainen J. Lannes G. Lebeau M. Ratner D. Serre Ya.G. Sinai N. J. A. Sloane J.Tits M. Waldschmidt S. Watanabe Managing Editors
M. Berger J. Coates S. R. S. Varadhan
Springer-Verlag Berlin Heidelberg GmbH
Peter Biirgisser Michael Clausen M. Amin Shokrollahi
Algebraic Complexity Theory With the Collaboration of Thomas Lickteig
With
21
Figures
Springer-Verlag Berlin Heidelberg GmbH
Peter Biirgisser
Mohammad Amin Shokrollahi
Institut fiir Mathematik Abt. Angewandte Mathematik Universităt Ziirich-Irchel WinterthurerstraBe 190 CH-8057 Ziirich, Switzerland
International Computer Science Institute 1947 Center Street, Suite 600 Berkeley, CA 94704-1105, USA and
[email protected]
Institut fiir Informatik V Bonn RomerstraBe 164 D-53117 Bonn, Germany Universităt
Michael Clausen Institut fiir Informatik V Universităt Bonn RomerstraBe 164 D-53117 Bonn, Germany
[email protected]
[email protected] By courtesy of the publisher, the poem "Der Zweifler" on page VII is reprinted from volume IV of Bertolt Brecht: Gesammelte Werke © Suhrkamp Verlag, Frankfurt am Main 1967. Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Biirgisser, Peter: Algebraic complexity theory 1 Peter Biirgisser; Michael Clausen; M. Amin Shokrollahi. With the collab. of Thomas Lickteig. - Berlin; Heidelberg; New York; Barcelona; Budapest; Hong Kong; London; Milan; Paris; Santa Clara; Singapore; Tokyo: Springer 1997 (Grundlehren der mathematischen Wissenschaften; 315) NE: Clausen, Michael:; Shokrollahi, Mohammad Amin:; GT
Mathematics Subject Classification (1991): 68Qxx, 05-XX, 14AI0, 14PI0, 15-XX, 16A46, 20CXX, 60C05, 65Fxx, 65T1o ISBN 978-3-642-08228-3 DOI 10.1007/978-3-662-03338-8
ISBN 978-3-662-03338-8 (eBook)
This work is subject to copyright. Ali rights are reserved, whether the whole or part ofthe material is concerned, specificallythe rights oftranslation, 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-Verlag. Violations are liable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 1997 Softcover reprint ofthe hardcover 18t edition 1997
Cover design: MetaDesign plus GmbH, Berlin Typesetting: Authors' input files edited and reformatted by Kurt Mattes, Heidelberg, using a Springer TEX macro-package SPIN: 10521707 41/3143-543210 Printed on acid-free paper
To Brigitte Claudia, Julia, Simone and Dorothe
DER ZWEIFLER
Irruner wenn uns Die Antwort auf eine Frage gefunden schien Loste einer von uns an der Wand die Schnur der alten AufgeroHten chinesischen Leinwand,
