Often, we use original expert estimates to compute estimates of related quantities. In many practical situations, it is desirable to know how accurate is the resulting estimate. There are many techniques for computing this accuracy: we can use simple probabilistic ideas and we can use simple fuzzy ideas. Strangely enough, these two reasonable techniques lead to drastically different results. Which of them is correct? Our practical tests show that none of these two methods is perfect: probabilistic approach usually underestimates uncertainty, while the fuzzy approach overestimates it. This looks similar to many cases that motivated Zadeh to promote the idea of soft computing – a combination of different uncertainty techniques. To get a more adequate combination technique, we analyzed the general problem of combining accuracy estimates and came up with a 1-parametric family of techniques that contains probabilistic and fuzzy as particular cases – and that indeed works better on several practical examples that each of the original two techniques.

Abstract A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x). f is a k(n)-enumerator if for every input x of length n. h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A.

To design data processing algorithms with the smallest average processing time, we need to know what this "average" stands for. At first glance, it may seem that real-life data are really "chaotic", and no probabilities are possible at all: today, we may apply our software package to elementary particles, tomorrow - to distances between the stars, etc. However, contrary to this intuitive feeling, there are stable probabilities in real-life data. This fact was first discovered in 1881 by Simon Newcomb who noticed that the first pages of logarithm tables (that contain numbers starting with 1) are more used than the last ones (that contain numbers starting with 9). To check why, he took all physical constants from a reference book, and counted how many of them start with 1. An intuitive expectation is that all 9 digits should be equally probable. In reality, instead of 11 %, about 30% of these constants turned out to be starting with 1. In general, the fraction or constants that start with a digit d can be described as ln(d + 1) - ln(d). We describe a new interval computations-related explanation for this empirical fact, and we explain its relationship with lifetime of the Universe and with the general problem of determining subjective (fuzzy) probabilities on finite and infinite intervals.

We give a new definition of resource bounded measure based on compressibility of infinite binary strings. We prove that the new definition is equivalent to the one commonly used. This new characterization offers us a different way to look at resource bounded measure, shedding more light on the meaning of measure zero results and providing one more tool to prove such results. The main contribution of the paper is the new definition and the proofs leading to the equivalence result. We then show how this new characterization can be used to prove that the class of linear autoreducible sets has p- measure 0. We also prove that the class of sets that are truth-table reducible to a p-selective set has p-measure 0 and that the class of sets that Turing reduce to a subpolynomial dense set has p-measure 0. This strengthens various results.

Polynomials over finite fields are used to show that any sparse set can conjunctively reduce to a tally set. This leads to new results and to simple proofs of known results about various classes that lie between P and P/poly.

Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following: Applications of the main theorem to log-truth-table and log-Turing reductions of NP sets to sparse sets. One typical example is that if SAT is log-truth-table reducible to a sparse set then NP is contained in DTIME (2O(log2n)). Generalizations of the main theorem which yields results similar to the main result at arbitrary levels of the polynomial hierarchy and which extend as well to strong nondeterministic reductions. The construction of an oracle relative to which P ≠ NP but there are NP-complete sets which are f(n)-tt-reducible to a tally set, for any f(n) ε ω(log n). This implies that, up to relativization, some of our results are optimal.

Queues, stacks, and tapes are basic concepts that have direct applications in compiler design and the general design of algorithms. Whereas stacks (pushdown store or last-in–first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-in-first-out storage). In this paper a comprehensive study comparing queues to stacks and tapes (off-line and with a one-way input tape) is presented. The techniques used rely on Kolmogorov complexity. In particular, one queue and one tape (or stack) are incomparable: (1) Simulating one stack (and hence one tape) by one queue requires $\Omega (n^{4/3} /\log n)$ time in both the deterministic and the nondeterministic cases. A corollary of this lower bound states that for this model of one-queue machines, nondeterministic linear time is not closed under complement. (2) Simulating one queue by one tape requires $\Omega (n^2 )$ time in the deterministic case and requires $\Omega (n^{4/3}/(\log n)^{2/3} )$ in the nondeterministic case. The paper further compares the relative power between different numbers of queues: (3) Simulating two queues (or two tapes) by one queue requires $\Omega (n^2 )$ time in the deterministic case, and $\Omega (n^2 /(\log ^2 n\log \log n))$ in the nondeterministic case. The deterministic bound is tight. The nondeterministic one is almost tight. The upper bounds for queues are also obtained.