Computational Complexity and Feasibility of Data Processing and Interval Computations
Targeted audience • Specialists in numerical computations, especially in numerical optimiza tion, who are interested in designing algorithms with automatie result ver ification, and who would therefore be interested in knowing how general their algorith
- PDF / 57,227,939 Bytes
- 460 Pages / 481.89 x 691.654 pts Page_size
- 60 Downloads / 332 Views
Applied Optimization Volume 10 Series Editors: Panos M. Pardalos University oi Florida, U.S.A.
Donald Hearn University oi Florida, U.SA.
The titles published in this series are listed at the end 0/ this volurne.
Computational Complexityand Feasibility of Data Processing and Interval Computations by
Vladik Kreinovich University ofTexas at EI Paso, Texas, U.S.A.
Anatoly Lakeyev Computing Center, Russian Academy of Sciences, Irkutsk, Russia
JiiiRohn Charles University and Academy of Sciences, Prague, Czech Republic
Patrick Kahl IBM, Tueson, Arizona, U.S.A.
Springer-Science+Business Media, B.V.
A C.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4785-7 ISBN 978-1-4757-2793-7 (eBook) DOI 10.1007/978-1-4757-2793-7
Printed on acid-free paper
All Rights Reserved © 1998 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1998. Softcover reprint ofthe hardcover 1st edition 1998 No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, inc1uding photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner.
CONTENTS
PREFACE 1
2 3
4
5
6
IX
INFORMAL INTRODUCTION: DATA PROCESSING, INTERVAL COMPUTATIONS, AND COMPUTATIONAL COMPLEXITY
1
THE NOTIONS OF FEASIBILITY AND NP-HARDNESS: BRIEF INTRODUCTION
23
IN THE GENERAL CASE, THE BASIC PROBLEM OF INTERVAL COMPUTATIONS IS INTRACTABLE
41
BASIC PROBLEM OF INTERVAL COMPUTATIONS FOR POLYNOMIALS OF A FIXED NUMBER OF VARIABLES
53
BASIC PROBLEM OF INTERVAL COMPUTATIONS FOR POLYNOMIALS OF FIXEDORDER
71
BASIC PROBLEM OF INTERVAL COMPUTATIONS FOR POLYNOMIALS WITH BOUNDED COEFFICIENTS
79
v
COMPLEXITY OF INTERVAL COMPUTATIONS
VI
7 8
9
FIXED DATA PROCESSING ALGORITHMS, VARYING DATA: STILL NP-HARD
83
FIXED DATA, VARYING DATA PROCESSING ALGORITHMS: STILL INTRACTABLE
85
WH AT IF WE ONLY ALLOW SOME ARITHMETIC OPERATIONS IN DATA PROCESSING?
87
10 FOR FRACTIONALLY-LINEAR
FUNCTIONS, A FEASIBLE ALGORITHM SOLVES THE BASIC PROBLEM OF INTERVAL COMPUTATIONS
91
11 SOLVING INTERVAL LINEAR SYSTEMS IS
NP-HARD
12 INTERVAL LINEAR. SYSTEMS: SEARCH FOR FEASIBLE CLASSES
99 111
13 PHYSICAL COROLLARY: PREDICTION
IS NOT ALWAYS POSSIBLE, EVEN FOR LINEAR SYSTEMS WITH KNOWN DYNAMICS
143
14 ENGINEERING COROLLARY: SIGNAL
PROCESSING IS NP-HARD
153
15 BRIGHT SIDES OF NP-HARDNESS
OF INTERVAL COMPUTATIONS I: NP-HARD MEANS THAT GOOD INTERVAL HEURISTICS CAN SOLVE OTHER HARD PROBLEMS
159
Contents
VII
16 IF INPUT INTERVALS ARE NARROW ENOUGH,THENINTERVAL COMPUTATIONS ARE ALMOST ALWAYS EASY
161
17 OPTIMIZATION - A FIRST EXAMPLE OF A NUMERICAL PROBLEM IN WHICH INTERVAL METHODS ARE USED: COMPUTATIONAL COMPLEXITY AND FEASIBILITY
173
18 SOLVING SYSTEMS OF EQUATIONS
197
19 APPROXIMATION OF INTERVAL FUNCTIONS
207
20 SOLVING DIFFERENTIAL EQUATIONS
219
21 PROPERTIES OF INTERVAL MATRICES I: MAIN RESULTS
225
22 PROPERTIES OF INTERV
