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.     

Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity

Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than H(\frac 12+d)\mathcal {H}(\frac {1}{2}+\delta) (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ. We also prove an analogous result for finite strings.     

Relations between Average-Case and Worst-Case Complexity

The consequences of the worst-case assumption NP=P are very well understood. On the other hand, we only know a few consequences of the analogous average-case assumption “NP is easy on average.” In this paper we establish several new results on the worst-case complexity of Arthur-Merlin games (the class AM) under the average-case complexity assumption “NP is easy on average.”

Nonreducible Descriptions for the Conditional Kolmogorov Complexity

Assume that a program p produces an output string b for an input string a: p(a) = b. We look for a “reduction” (simplification) of p, i.e., a program q such that q(a) = b but q has Kolmogorov complexity smaller than p and contains no additional information as compared to p (this means that the conditional complexity K(q|p) is negligible). We show that, for any two strings a and b (except for some degenerate cases), one can find a nonreducible program p of any arbitrarily large complexity (any value larger than K(a) + K(b|a) is possible).     

Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets

We study constructive and resource-bounded scaled dimension as an information content measure and obtain several results that parallel previous work on unscaled dimension. Scaled dimension for finite strings is developed and shown to be closely related to Kolmogorov complexity. The scaled dimension of an infinite sequence is characterized by the scaled dimensions of its prefixes. We obtain an exact Kolmogorov complexity characterization of scaled dimension. Juedes and Lutz (Inf. Comput. 125(1), 13–31, 1996) established a small span theorem for P/poly-Turing reductions which asserts that for any problem A in ESPACE, either the class of problems reducible to A (the lower span) or the class of problems to which A is reducible (the upper span) has measure 0 in ESPACE. We apply our Kolmogorov complexity characterization to improve this to (?3)rd-order scaled dimension 0 in ESPACE. As a consequence we obtain a new upper bound on the Kolmogorov complexity of Turing-hard sets for ESPACE.     

Relating and Contrasting Plain and Prefix Kolmogorov Complexity

In (Bauwens and Shen, J. Symb. Log. 79(2), 620–632, 2013) a short proof is given that some strings have maximal plain Kolmogorov complexity but not maximal prefix-free complexity. We argue that the proof technique is useful to simplify existing proofs and to solve open questions. We present a short proof of a result due to Robert Solovay that relates plain and prefix complexity:     

On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions

The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions, one of them is the Boolean isomorphism relation. Most of these computational problems turn out to be between co-NP and ^p ₂ . Received July 1996, and in final form March 1998.     

Graph Complexity and Slice Functions

Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, Rödl, and Savický [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(?) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of $\exp((\log \log n)^{\omega(1)})$ would give an explicit language outside the class Σ ₂ ^cc of the two-party communication complexity as defined by Babai, Frankl, and Simon [BFS]. Our lower bound proof is based on sign-representing polynomials for DNFs and lower bounds on ranks of ±1 matrices even after being subjected to sign-preserving changes to their entries. For the former, we use a result of Nisan and Szegedy [NS] and an idea from a recent result of Klivans and Servedio [KS]. For the latter, we use a recent remarkable lower bound due to Forster [F1].     

Graph Complexity and Slice Functions

   Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, R?dl, and Savicky [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(ℓ) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of

A Tight Upper Bound on Kolmogorov Complexity and Uniformly Optimal Prediction

This paper links the concepts of Kolmogorov complexity (in complexity theory) and Hausdorff dimension (in fractal geometry) for a class of recursive (computable) ω -languages. It is shown that the complexity of an infinite string contained in a Σ ₂ -definable set of strings is upper bounded by the Hausdorff dimension of this set and that this upper bound is tight. Moreover, we show that there are computable gambling strategies guaranteeing a uniform prediction quality arbitrarily close to the optimal one estimated by Hausdorff dimension and Kolmogorov complexity provided the gambler's adversary plays according to a sequence chosen from a Σ ₂ -definable set of strings. We provide also examples which give evidence that our results do not extend further in the arithmetical hierarchy. Received February 1995, and in revised form February 1997, and in final form October 1997.     

Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers

We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and wherethey are fundamentally different. We discuss and relate the basicnotions of both theories: Shannon entropy, Kolmogorov complexity, Shannon mutual informationand Kolmogorov (``algorithmic') mutual information. We explainhow universal coding may be viewed as a middle ground betweenthe two theories. We consider Shannon's rate distortion theory, whichquantifies useful (in a certain sense) information.We use the communication of information as our guiding motif, and we explain howit relates to sequential question-answer sessions.     

二元关系的性质测试及其复杂性分析

本文介绍了性质测试的基本原理,分析了用性质测试方法解决参数化问题的可行性,并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题,对固定的距离参数,证明了测试复杂性低于标准判定程序的复杂性。     

Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences

The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1.     

Space Functions and Space Complexity of the Word Problem in Semigroups

We introduce the space function s(n) of a finitely presented semigroup ${S =\langle A \mid R \rangle}$ . To define s(n) we consider pairs of words w,w′ over A of length at most n equal in S and use relations from R for the derivations ${w = w_0 \rightsquigarrow \dots \rightsquigarrow w_t = w'; s(n)}$ bounds from above the lengths of the words w _i at intermediate steps, i.e., the space sufficient to implement all such transitions ${w \rightsquigarrow \dots \rightsquigarrow w'}$ . One of the results obtained is the following criterion: A finitely generated semigroup S has decidable word problem of polynomial space complexity if and only if S is a subsemigroup of a finitely presented semigroup H with polynomial space function.     

Variance and Bias for General Loss Functions

When using squared error loss, bias and variance and their decomposition of prediction error are well understood and widely used concepts. However, there is no universally accepted definition for other loss functions. Numerous attempts have been made to extend these concepts beyond squared error loss. Most approaches have focused solely on 0-1 loss functions and have produced significantly different definitions. These differences stem from disagreement as to the essential characteristics that variance and bias should display. This paper suggests an explicit list of rules that we feel any reasonable set of definitions should satisfy. Using this framework, bias and variance definitions are produced which generalize to any symmetric loss function. We illustrate these statistics on several loss functions with particular emphasis on 0-1 loss. We conclude with a discussion of the various definitions that have been proposed in the past as well as a method for estimating these quantities on real data sets.     

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c^d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.     

Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions

The two-party communication complexity of Boolean function f is known to be at least log rank (M _f ), i.e., the logarithm of the rank of the communication matrix of f [19]. Lovász and Saks [17] asked whether the communication complexity of f can be bounded from above by (log rank (M _f )) ^c , for some constant c . The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f , it remained a difficult open problem. We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L ₁ norm of function f , for arbitrary Boolean function f . Received August 24, 1996; revised October 15, 1997.