Digital Commons Network^™

Why Encubation?, Vladik Kreinovich, Rohan Baingolkar, Swapnil S. Chauhan, Ishtjot S. Kamboj

Departmental Technical Reports (CS)

It is known that some algorithms are feasible, and some take too long to be practical/ For example, if the running time of an algorithm is 2ⁿ, where n = len(x) is the bit size of the input x, then already for n = 500, the computation time exceeds the lifetime of the Universe. In computer science, it is usually assumed that an algorithm A is feasible if and only if it is polynomial-time, i.e., if its number of computational steps t_A(x) on any input x is bounded by a polynomial P(n) of the input …

Towards An Efficient Bisection Of Ellipsoids, Paden Portillo, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Constraints are often represented as ellipsoids. One of the main advantages of such constrains is that, in contrast to boxes, over which optimization of even quadratic functions is NP-hard, optimization of a quadratic function over an ellipsoid is feasible. Sometimes, the area described by constrains is too large, so it is reasonable to bisect this area (one or several times) and solve the optimization problem for all the sub-areas. Bisecting a box, we still get a box, but bisecting an ellipsoid, we do not get an ellipsoid. Usually, this problem is solved by enclosing the half-ellipsoid in a larger ellipsoid, …

Estimating Information Amount Under Uncertainty: Algorithmic Solvability And Computational Complexity, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

Measurement results (and, more generally, estimates) are never absolutely accurate: there is always an uncertainty, the actual value x is, in general, different from the estimate X. Sometimes, we know the probability of different values of the estimation error dx=X-x, sometimes, we only know the interval of possible values of dx, sometimes, we have interval bounds on the cdf of dx. To compare different measuring instruments, it is desirable to know which of them brings more information - i.e., it is desirable to gauge the amount of information. For probabilistic uncertainty, this amount of information is described by Shannon's entropy; …

M Solutions Good, M-1 Solutions Better, Luc Longpre, William Gasarch, G. W. Walster, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main objectives of theoretical research in computational complexity and feasibility is to explain experimentally observed difference in complexity.

Empirical evidence shows that the more solutions a system of equations has, the more difficult it is to solve it. Similarly, the more global maxima a continuous function has, the more difficult it is to locate them. Until now, these empirical facts have been only partially formalized: namely, it has been shown that problems with two or more solutions are more difficult to solve than problems with exactly one solution. In this paper, we extend this result and show …

Estimating Information Amount Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Gang Xiang, Olga Kosheleva, George J. Klir

Departmental Technical Reports (CS)

In most real-life situations, we have uncertainty: we do not know the exact state of the world, there are several (n) different states which are consistent with our knowledge. In such situations, it is desirable to gauge how much information we need to gain to determine the actual state of the world. A natural measure of this amount of information is the average number of "yes"-"no" questions that we need to ask to find the exact state. When we know the probabilities p1,...,pn of different states, then, as Shannon has shown, this number of questions can be determined as S=-p1 …

Towards Combining Probabilistic And Interval Uncertainty In Engineering Calculations: Algorithms For Computing Statistics Under Interval Uncertainty, And Their Computational Complexity, Vladik Kreinovich, Gang Xiang, Scott A. Starks, Luc Longpre, Martine Ceberio, Roberto Araiza, J. Beck, R. Kandathi, A. Nayak, R. Torres, J. Hajagos

Departmental Technical Reports (CS)

In many engineering applications, we have to combine probabilistic and interval uncertainty. For example, in environmental analysis, we observe a pollution level x(t) in a lake at different moments of time t, and we would like to estimate standard statistical characteristics such as mean, variance, autocorrelation, correlation with other measurements. In environmental measurements, we often only measure the values with interval uncertainty. We must therefore modify the existing statistical algorithms to process such interval data.

In this paper, we provide a survey of algorithms for computing various statistics under interval uncertainty and their computational complexity. The survey includes both known …

The Challenge Of Hyper-Spectral Satellite Imaging And Integer-Valued Fuzzy Sets, Maria Beltran, Vladik Kreinovich, Scott A. Starks

Departmental Technical Reports (CS)

Satellite images already produce huge amounts of data, which makes their processing a serious computational challenge. This problem will become even more complicated with the launch of multi-spectral Earth-imaging satellites that will increase the amount of information by at least two orders of magnitude. With such a huge amount of information, it is necessary to come up with data processing methods that are as fast as possible. In particular, we show that for fuzzy processing techniques, this leads to the necessity to use integer-valued fuzzy sets.