文档介绍：Texts puter Science
Editors
David Gries
Fred B. Schneider
For further volumes:
ies/3191
Steven Homer • Alan L. Selman
Computability and
Complexity Theory
Second Edition
123
Steven Homer Alan L. Selman
Computer Science Department Department puter Science
Boston University and Engineering
Boston Massachusetts University at Buffalo
USA The State University of New York
******@ Buffalo New York
USA
******@
Series Editors
David Gries Fred B. Schneider
Department puter Science Department puter Science
Upson Hall Upson Hall
Cornell University Cornell University
Ithaca, NY 14853-7501, USA Ithaca, NY 14853-7501, USA
ISSN 1868-0941 e-ISSN 1868-095X
ISBN 978-1-4614-0681-5 e-ISBN 978-1-4614-0682-2
DOI -1-4614-0682-2
Springer New York Dordrecht Heidelberg London
Library of Congress Control Number: 2011941200
© Springer Science+Business Media, LLC 2011
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,
NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in
connection with any form of information storage and retrieval, electronic adaptation, computer software,
or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are
not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject
to proprietary rights.
Printed on acid-free paper
Springer is part of Springer Science+Business Media ()
We dedicate this book to our wives,
Michelle and Sharon
Preface to the First Edition 2001
The theory puting puter science with concepts, models, and
formalisms for reasoning about both the resources needed to carry putations
and the efficiency of putations that use