Physical Sciences and Mathematics Commons^™

For Discrete-Time Linear Dynamical Systems Under Interval Uncertainty, Predicting Two Moments Ahead Is Np-Hard, Luc Jaulin, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In the first approximation, when changes are small, most real-world systems are described by linear dynamical equations. If we know the initial state of the system, and we know its dynamics, then we can, in principle, predict the system's state many moments ahead. In practice, however, we usually know both the initial state and the coefficients of the system's dynamics with some uncertainty. Frequently, we encounter interval uncertainty, when for each parameter, we only know its range, but we have no information about the probability of different values from this range. In such situations, we want to know the range …

While, In General, Uncertainty Quantification (Uq) Is Np-Hard, Many Practical Uq Problems Can Be Made Feasible, Anderson Gray, Scott Ferson, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In general, many general mathematical formulations of uncertainty quantification problems are NP-hard, meaning that (unless it turned out that P = NP) no feasible algorithm is possible that would always solve these problems. In this paper, we argue that if we restrict ourselves to practical problems, then the correspondingly restricted problems become feasible -- namely, they can be solved by using linear programming techniques.

Computational Complexity Of Experiment Design In Civil Engineering, Olga Kosheleva, Yan Wang, Vladik Kreinovich

Departmental Technical Reports (CS)

To guarantee reliability and safety of engineering structures, we need to regularly measure their mechanical properties. Such measurements are often expensive and time-consuming. It is therefore necessary to carefully plan the corresponding measurement experiments, to minimize the corresponding expenses.

It is known that, in general, experiment design is NP-hard. However, the previous proofs dealt either with nonlinear systems, or with situations with low measurement accuracy. In civil engineering, however, most systems are well-described by linear systems, and measurements are reasonably accurate. In this paper, we show that experiment design is NP-hard even for civil engineering problems. We show that even …

Solving Interval Linear Systems Is Np-Hard Even When All Inputs Are Known With The Same Accuracy, Ralph Kelsey, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that in general, solving interval linear systems is NP-hard. There exist several proofs of this NP-hardness, and all these proofs use examples with intervals of different width -- corresponding to different accuracy in measuring different coefficients. For some classes of interval linear systems with the same accuracy, feasible algorithms are known. We show, however, that in general, solving interval linear systems is NP-hard even when all inputs are known with the same accuracy.

Checking Monotonicity Is Np-Hard Even For Cubic Polynomials, Andrzej Pownuk, Luc Longpre, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main problems of interval computations is to compute the range of a given function over given intervals. In general, this problem is computationally intractable (NP-hard) -- that is why we usually compute an enclosure and not the exact range. However, there are cases when it is possible to feasibly compute the exact range; one of these cases is when the function is monotonic with respect to each of its variables. The monotonicity assumption holds when the derivatives at a midpoint are different from 0 and the intervals are sufficiently narrow; because of this, monotonicity-based estimates are often …