[(Computational Complexity and Feasibility of Data by Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl

By Vladik Kreinovich, Anatoly Lakeyev, Jiří Rohn, Patrick Kahl (auth.)

Targeted viewers • experts in numerical computations, specifically in numerical optimiza­ tion, who're attracted to designing algorithms with automatie outcome ver­ ification, and who could accordingly have an interest in understanding how normal their algorithms caIi in precept be. • Mathematicians and laptop scientists who're drawn to the speculation zero/ computing and computational complexity, particularly computational com­ plexity of numerical computations. • scholars in utilized arithmetic and laptop technological know-how who're drawn to computational complexity of other numerical equipment and in studying normal recommendations for estimating this computational complexity. The ebook is written with all motives and definitions further, in order that it may be used as a graduate point textbook. What this ebook .is approximately information processing. in lots of real-life events, we're attracted to the worth of a actual volume y that's diflicult (or even most unlikely) to degree without delay. for instance, it truly is most unlikely to at once degree the quantity of oil in an oil box or a distance to a celeb. considering we can't degree such amounts without delay, we degree them not directly, by way of measuring another amounts Xi and utilizing the recognized relation among y and Xi'S to reconstruct y. The set of rules that transforms the implications Xi of measuring Xi into an estimate fj for y is termed info processing.

Show description

Read or Download [(Computational Complexity and Feasibility of Data Processing and Interval Computations )] [Author: Vladik Kreinovich] [Dec-2010] PDF

Similar nonfiction_8 books

Superlattices and Other Heterostructures: Symmetry and Optical Phenomena

Superlattices and different Heterostructures bargains with the optical homes of superlattices and quantum good buildings with emphasis on phenomena ruled through crystal symmetries. After a quick advent to workforce idea and symmetries, equipment for calculating spectra of electrons, excitons, and phonons in heterostructures are mentioned.

Masses of Fundamental Particles: Cargèse 1996

Boson lots within the typical version; D. Treille. Non-Commutative Geometry and the interior house of Gauge Theories; T. Krajewski. most sensible Quark Mass; J. L. Rosner. Unified Theories of Flavour with U(2) as Horizontal team; A. Romanino. Heavy-Quark plenty; M. Neubert. Light-Quark plenty; H. Leutwyler. vulnerable Matrix parts at the Lattice: contemporary advancements in K-Physics; M.

Extra resources for [(Computational Complexity and Feasibility of Data Processing and Interval Computations )] [Author: Vladik Kreinovich] [Dec-2010]

Example text

In other words, floating-point formulations contain extra complexity that is unrelated to the complexity of data processing and interval computations; thus, if we try to reformulate our results in terms of floating point numbers, the resulting combination of two complexities would make the corresponding results very un-intuitive. 4. Second Step Towards Formalization 0/ Feasibility: Computer-Independent Notion 0/ Computation Time General idea. , hardware-supported simple operations such as operations with bits, or addition, etc.

Instead of the original Gaganov's proof, we will use a simpler proof (inspired by Vavasis [418]). First, we will show that the exact basic problem of interval computations is NP-hard. To prove this result, we will show that if we are able to compute the desired interval y for quadratic polynomials f( Zl, ... , zn), then we will be able to solve propositional satisfiability problem for 3-CNF formulas. Since satisfiability problem is known to be NP-hard, we will thus prove that our problem is also NP-hard.

The algorithm proposed by Tarski (and later modified by Seidenberg and others; see Chapter 4 for more details) takes as input an arbitrary formula F that can be obtained from the polynomial equalities fi(Zl, ... , zn) 0 and inequalities f; (Zl> ... , zn) 0 (in which Ii(Zb ... , zn) and f;(Zl> ... , zn) are polynomials with integer or rational coefficients) by adding logical connectives ("and", "or", "not", "implies"), and quantifiers Vz and 3z that run over all real numbers. In particular, the upper endpoint y of the range f(Xl, ...

Download PDF sample

Rated 4.43 of 5 – based on 14 votes