On the definitions of some complexity classes of real numbers

Three formulations of computable real numbers based on the concepts of Cauchy sequences, Dedekind cuts, and the binary expansions have been carefully studied. We extend the definitions to recursively enumerable real numbers, and some complexity-bounded classes of real numbers. In particular, polynomial time and nondeterministic polynomial time computable real numbers are defined and compared. Although the three definitions are equivalent for the class of recursive real numbers, they are not equivalent for other classes of real numbers. It seems that the definition based on the concept of Cauchy sequences is the most general one.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Constructive dimension equals Kolmogorov complexity

We derive the coincidence of Lutz's constructive dimension and Kolmogorov complexity for sets of infinite strings from Levin's early result on the existence of an optimal left computable cylindrical semi-measure M via simple calculations.     

Kolmogorov complexity of enumerating finite sets

Solovay [R.M. Solovay, On random R.E. sets, in: A.I. Arruda, N.C.A. da Costa, R. Chaqui (Eds.), Non-Classical Logics, Model Theory and Computability, North-Holland, Amsterdam, 1977, pp. 283-307] has proved that the minimal length of a program enumerating a set A is upper bounded by 3 times the negative logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. In this paper, we show that the constant 3 can be replaced by the constant 2 for finite sets A.     

NL-printable sets and nondeterministic Kolmogorov complexity

P-printable sets were defined by Hartmanis and Yesha and have been investigated by several researchers. The analogous notion of L-printable sets was defined by Fortnow et al.; both P-printability and L-printability were shown to be related to notions of resource-bounded Kolmogorov complexity. Nondeterministic logspace (NL)-printability was defined by Jenner and Kirsig, but some basic questions regarding this notion were left open. In this paper we answer a question of Jenner and Kirsig by providing a machine-based characterization of the NL-printable sets.     

Sets with small generalized Kolmogorov complexity

Summary We study the class of sets with small generalized Kolmogorov complexity. The following results are established: 1. A set has small generalized Kolmogorov complexity if and only if it is semi-isomorphic to a tally set. 2. The class of sets with small generalized Kolmogorov complexity is properly included in the class of self-p-printable sets. 3. The class of self-p-printable sets is properly included in the class of sets with selfproducible circuits. 4. A set S has self-producible circuits if and only if there is a tally set T such that P(T)=P(S). 5. If a set S has self-producible circuits, then NP(S)=NP _B(S), where NP _B( ) is the restriction of NP( ) studied by Book, Long, and Selman [4]. 6. If a set S is such that NP(S) =NP _B(S), then NP(S) P(SSAT).     

Non-reducible descriptions for conditional Kolmogorov complexity

Assume that a program p$p$ on input a$a$ outputs b$b$. We are looking for a shorter program q$q$ having the same property (q(a)=b$q\left(a\right)=b$). In addition, we want q$q$ to be simple conditional to p$p$ (this means that the conditional Kolmogorov complexity K(q|p)$K\left(q\right|p)$ is negligible). In the present paper, we prove that sometimes there is no such program q$q$, even in the case when the complexity of p$p$ is much bigger than K(b|a)$K\left(b\right|a)$. We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively.     

Average-case analysis of algorithms using Kolmogorov complexity

Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science.In the past few years,we have demonstrated that Kolmogorov complexity is an improtant tool for analyzing the average-case complexity of algorithms.We have developed the incompressibility method.In this paper,sereral simple examples are used to further demonstrate the power and simplicity of such method.We prove bounds on the average-case number of stacks(queues)required for sorting sequential or parallel Queuesort or Stacksort.     

Stability of properties of Kolmogorov complexity under relativization

Assume that a tuple of binary strings \(\bar a\) = 〈a ₁ ..., a _n 〉 has negligible mutual information with another string b. Does this mean that properties of the Kolmogorov complexity of \(\bar a\) do not change significantly if we relativize them to b? This question becomes very nontrivial when we try to formalize it. In this paper we investigate this problem for a special class of properties (for properties that can be expressed by an ?-formula). In particular, we show that a random (conditional on \(\bar a\)) oracle b does not help to extract common information from the strings a _i .     

On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (in contrast to the Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials.A partial extension of Vincent’s Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.     

基于Kolmogorov复杂性的垃圾图像分类模型*

为了进一步遏制图像型垃圾邮件的泛滥,本文首次提出了一种基于Kolmogorov复杂性的垃圾图像分类模型。该模型利用数据压缩技术,实现了对垃圾图像的有效分类。与目前主流垃圾图像分类方法相比,本模型既不需要提取图像中的文字,也不需要对图像特征进行定义和选择,而是一种无参数的分类方法。实验验证了本模型的有效性和鲁棒性,同时还表明,Kolmogorov复杂性在垃圾信息过滤中具有广阔的应用前景。     

Statistical properties of finite sequences with high Kolmogorov complexity

We investigate to what extent finite binary sequences with high Kolmogorov complexity are normal (all blocks of equal length occur equally frequently), and the maximal length of all-zero or all-one runs which occur with certainty.Ming Li was supported by NSERC Operating Grant OGP-046506. Paul Vitányi was partially supported by NSERC International Scientific Exchange Award ISE0046203 and by the NWO through NFI Project ALADDIN under Contract Number NF 62-376.     

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.     

一种基于柯氏复杂度的因果网络定向方法

因果网络定向问题实质是一个多对多因果关系发现过程,传统的V-结构定向方法只能确定一组马尔可夫等价类而非最终的因果关系.为解决该问题,从柯氏复杂度的因果推断原理视角出发,利用贝叶斯链式法则推导出局部网络因果定向规则,并在此基础上提出高维全局网络因果定向方法.同时,将前者运用于改进基于局部条件独立信息搜索学习马尔可夫毯...     

On data mining,compression, and Kolmogorov complexity

Will we ever have a theory of data mining analogous to the relational algebra in databases? Why do we have so many clearly different clustering algorithms? Could data mining be automated? We show that the answer to all these questions is negative, because data mining is closely related to compression and Kolmogorov complexity; and the latter is undecidable. Therefore, data mining will always be an art, where our goal will be to find better models (patterns) that fit our datasets as best as possible.     

Computational complexity of real functions

Recursive analysis, the theory of computation of functions on real numbers, has been studied from various aspects. We investigate the computational complexity of real functions using the methods of recursive function theory. Partial recursive real functions are defined and their domains are characterized as the recursively open sets. We define the time complexity of recursive real continuous functions and show that the time complexity and the modulus of uniform continuity of a function are closely related. We study the complexity of the roots and the differentiability of polynomial time computable real functions. In particular, a polynomial time computable real function may have a root of arbitrarily high complexity and may be nowhere differentiable. The concepts of the space complexity and nondeterministic computation are used to study the complexity of the integrals and the maximum values of real functions. These problems are shown to be related to the “P=?NP” and the “P=?PSPACE” questions.