Time-Bounded Kolmogorov Complexity and Solovay Functions

A Solovay function is an upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of computable Solovay functions by showing that for some constant c ₀ and all computable functions t such that c ₀ n??t(n), the time-bounded version K ^t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if ?? _g =??2^?g(n) is Martin-Löf random. We obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin??s ?? extends to the time-bounded case in so far as $\Omega _{ \textnormal{K}^{t}}$ is Martin-Löf random for any t as above. As a step in the direction of a characterization of K-triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is O(g(n)?K(n))-jump traceable for all computable Solovay functions g. Furthermore, this equivalence remains true when the universal quantification over all computable Solovay functions in the second statement is restricted either to all functions of the form K ^t for some function t as above or to a single function K ^t of this form. Finally, we investigate into the plain Kolmogorov complexity C and its time-bounded variant C ^t of initial segments of computably enumerable sets. Our main theorem here asserts that every high c.e. Turing degree contains a c.e. set B such that for any computable function t there is a constant c _t >0 such that for all m it holds that C ^t (B?m)??c _t ?m, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C ^t (A?m)??logm+c. By similar methods it can be shown that any high degree contains a set B such that C ^t (B?m)??⁺ m/4. The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes et al. (Theor. Comput. Sci. 132(1?C2):37?C70, 1994) that every high degree contains a strongly deep set.     

Extracting Kolmogorov complexity with applications to dimension zero-one laws

We apply results on extracting randomness from independent sources to “extract” Kolmogorov complexity. For any α,?>0, given a string x with K(x)>α|x|, we show how to use a constant number of advice bits to efficiently compute another string y, |y|=Ω(|x|), with K(y)>(1-?)|y|. This result holds for both unbounded and space-bounded Kolmogorov complexity.We use the extraction procedure for space-bounded complexity to establish zero-one laws for the strong dimensions of complexity classes within ESPACE. The unbounded extraction procedure yields a zero-one law for the constructive strong dimensions of Turing degrees.     

Parabolic equations with double variable nonlinearities

The paper is devoted to the study of the homogeneous Dirichlet problem for the doubly nonlinear parabolic equation with nonstandard growth conditions:

ut=div(a(x,t,u)|u^|α(x,t)|∇u^|p(x,t)−2∇u)+f(x,t)     

Predictive complexity and information

The notions of predictive complexity and of corresponding amount of information are considered. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. We consider predictive complexity for a wide class of bounded loss functions which are generalizations of square-loss function. Relations between unconditional KG(x) and conditional KG(x|y) predictive complexities are studied. We define an algorithm which has some “expanding property”. It transforms with positive probability sequences of given predictive complexity into sequences of essentially bigger predictive complexity. A concept of amount of predictive information IG(y:x) is studied. We show that this information is noncommutative in a very strong sense and present asymptotic relations between values IG(y:x), IG(x:y), KG(x) and KG(y).     

Avoiding Simplicity is Complex

It is a trivial observation that every decidable set has strings of length n with Kolmogorov complexity log?n+O(1) if it has any strings of length n at all. Things become much more interesting when one asks whether a similar property holds when one considers resource-bounded Kolmogorov complexity. This is the question considered here: Can a feasible set A avoid accepting strings of low resource-bounded Kolmogorov complexity, while still accepting some (or many) strings of length?n? More specifically, this paper deals with two notions of resource-bounded Kolmogorov complexity: Kt and KNt. The measure Kt was defined by Levin more than three decades ago and has been studied extensively since then. The measure KNt is a nondeterministic analog of Kt. For all strings x, Kt(x)??KNt(x); the two measures are polynomially related if and only if NEXP?EXP/poly (Allender et al. in J.?Comput. Syst. Sci. 77:14?C40, 2011). Many longstanding open questions in complexity theory boil down to the question of whether there are sets in P that avoid all strings of low Kt complexity. For example, the EXP vs ZPP question is equivalent to (one version of) the question of whether avoiding simple strings is difficult: (EXP=ZPP if and only if there exist ?>0 and a ??dense?? set in P having no strings x with Kt(x)??|x| ^? (Allender et al. in SIAM J. Comput. 35:1467?C1493, 2006)). Surprisingly, we are able to show unconditionally that avoiding simple strings (in the sense of KNt complexity) is difficult. Every dense set in NP??coNP contains infinitely many strings x such that KNt(x)??|x| ^? for every ?>0. The proof does not relativize. As an application, we are able to show that if E=NE, then accepting paths for nondeterministic exponential time machines can be found somewhat more quickly than the brute-force upper bound, if there are many accepting paths.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

Stochastic stabilization and destabilization

It is shown in this paper that any nonlinear systems in ^d can be stabilized by Brownian motion provided |ƒ(x,t)| ≤ K|x| for some K > 0. On the other hand, this system can also be destabilized by Brownian motion if the dimension d ≥ 2. Similar results are also obtained for any given stochastic differential equation dx(t) = ƒ(x(t), t) + g(x(t), t) dW(t).     

Time rescaling and asymptotic behavior of some fourth-order degenerate diffusion equations

In this paper, we investigate the large-times behavior of weak solutions to the fourth-order degenerate parabolic equation u_t = −(|u|ⁿu_xxx)_x modeling the evolution of thin films. In particular, for all n > 0, we prove exponential decay of u(x, t) towards its mean value (1/|Ω|) ∫_Ω u dx in L¹-norm for long times and we give the explicit (n-dependent) rate of decay. The result is based on classical entropy estimates, and on detailed lower bounds for the entropy production.     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

On the Autoreducibility of Functions

This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class C\mathcal{C} that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all C\mathcal{C} -complete languages are length-decreasing (logspace) self-reducible then C í P\mathcal{C}\subseteq \mathrm {P} (C í L\mathcal {C}\subseteq \mathrm {L} ). In particular, this result applies to NL, NP and PSPACE. We also prove an equivalent of this theorem for function classes (for example, for #P). We also show that for several hard function classes, in particular for #P, it is the case that all their complete functions are deterministically autoreducible. In particular, we show the following result. Let f be a #P parsimonious function with two preimages of 0. We show that there are two FP functions h and t such that for all inputs x we have f(x)=t(x)+f(h(x)), h(x)≠x, and t(x)∈{0,1}. Our results regarding single-query autoreducibility of #P functions can be contrasted with random self-reducibility for which it is known that if a #P complete function were random self-reducible with one query then the polynomial hierarchy would collapse.     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

Modeling Time-Bounded Prefix Kolmogorov Complexity

In the literature, prefix Kolmogorov complexity is defined either in terms of self-delimiting Turing machines or in terms of partial recursive prefix functions. These notions of prefix Kolmogorov complexity are equivalent because, as Chaitin showed, every partial recursive prefix function can be simulated by a self-delimiting Turing machine. However, the simulation given by Chaitin's construction is not efficient, and so questions regarding the time-bounded equivalence of these notions remained unresolved. Here we closely examine these questions. As our main result, we show that every partial recursive prefix function can be simulated with polynomial efficiency by a self-delimiting Turing machine if and only if P = NP. Thus, it is unlikely that Chaitin's construction can be used to show the polynomial-time equivalence of these notions of prefix Kolmogorov complexity. Here we further examine the relationships between these notions of time-bounded prefix Kolmogorov complexity. Received March 25, 1997, and in final form October 8, 1999.     

A measure of information gained through biometric systems

We propose a measure of information gained through biometric matching systems. Firstly, we discuss how the information about the identity of a person is derived from biometric samples through a biometric system, and define the “biometric system entropy” or BSE based on mutual information. We present several theoretical properties and interpretations of the BSE, and show how to design a biometric system which maximizes the BSE. Then we prove that the BSE can be approximated asymptotically by the relative entropy D(f_G(x)∥f_I(x)) where f_G(x) and f_I(x) are probability mass functions of matching scores between samples from individuals and among population. We also discuss how to evaluate the BSE of a biometric system and show experimental evaluation of the BSE of face, fingerprint and multimodal biometric systems.     

Some procedures for function approximation based on the use of sample data and their application in heuristic methods for solving practical problems

Let f(x) be a member of a set of functions over a probability space. Samples of f(x) are 2-tuples (xⁱ,f(xⁱ) where xⁱ is a sample of the random variable X and f(xⁱ) is a sample of f(x) at x = xⁱ. Some procedures and analysis are presented for the approximation of such functions by systems of orthonormal functions. The approximations are based on the data samples. The analysis includes the case of error in the measurement of f(xⁱ). The properties of the expected square error in the approximation are examined for a number of different estimators for the coefficients in the expansion and these well-behaved and easily analyzed estimators are compared to those obtained using the method of least squares. The effectiveness of different sets of basis functions, those involved in the Karhunen-Loeve expansion and others, can be compared and an approach is suggested to adaptive basis selection in order to select that basis which is most efficient in approximating the particular function under examination. The connection between results and applications are discussed in the introduction and conclusion.     

Realizing Boolean functions on disjoint sets of variables

For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f:{0,1}ⁿ→{0,1}ⁿ such that C(f×f)? (1+ε)C(f) and arbitrarily complex functions f:{0,1}ⁿ→{0,1} such that C(v°(fxf)? (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

The Sum 2KM(x)−K(x) Over All Prefixes x of Some Binary Sequence Can be Infinite

We consider two quantities that measure complexity of binary strings: KM(x) is defined as the negative logarithm of continuous a priori probability on the binary tree, and K(x) denotes prefix complexity of a binary string x. In this paper we answer a question posed by Joseph Miller and prove that there exists an infinite binary sequence ω such that the sum of 2^KM(x)?K(x) over all prefixes x of ω is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.     

Partition arguments in multiparty communication complexity

Consider the “Number in Hand” multiparty communication complexity model, where k players holding inputs x₁,…,x_k∈{0,1}ⁿ communicate to compute the value f(x₁,…,x_k) of a function f known to all of them. The main lower bound technique for the communication complexity of such problems is that of partition arguments: partition the k players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem.In this paper, we study the power of partition arguments. Our two main results are very different in nature:

(i)

For randomized communication complexity, we show that partition arguments may yield bounds that are exponentially far from the true communication complexity. Specifically, we prove that there exists a 3-argument function f whose communication complexity is Ω(n), while partition arguments can only yield an Ω(logn) lower bound. The same holds for nondeterministiccommunication complexity.

(ii)

For deterministic communication complexity, we prove that finding significant gaps between the true communication complexity and the best lower bound that can be obtained via partition arguments, would imply progress on a generalized version of the “log-rank conjecture” in communication complexity. We also observe that, in the case of computing relations (search problems), very large gaps do exist.

We conclude with two results on the multiparty “fooling set technique”, another method for obtaining communication complexity lower bounds.