Characterizing strong randomness via Martin-Löf randomness

We introduce two methods for characterizing strong randomness notions via Martin-Löf randomness. We apply these methods to investigate Schnorr randomness relative to 0?^′.     

Higher Kurtz randomness

A real x is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.     

The axiomatic power of Kolmogorov complexity

The famous Gödel incompleteness theorem states that for every consistent, recursive, and sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T  . In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter (unless NP=PSPACE$\mathrm{NP}=\mathrm{PSPACE}$).     

How much randomness is needed for statistics?

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle (which we call the “classical approach”). The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ (we call this approach “Hippocratic”). While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity.     

Lowness properties and randomness

The set A is low for (Martin-Löf) randomness if each random set is already random relative to A. A is K-trivial if the prefix complexity K of each initial segment of A is minimal, namely . We show that these classes coincide. This answers a question of Ambos-Spies and Ku?era in: P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000: each low for Martin-Löf random set is . Our class induces a natural intermediate ideal in the r.e. Turing degrees, which generates the whole class under downward closure.Answering a further question in P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000, we prove that each low for computably random set is computable.     

Oscillation in the initial segment complexity of random reals

We study oscillation in the prefix-free complexity of initial segments of 1-random reals. For upward oscillations, we prove that _∑n∈ω²−g(n) diverges iff (^∃∞n)K(X?n)>n+g(n) for every 1-random X∈ω². For downward oscillations, we characterize the functions g such that (^∃∞n)K(X?n)<n+g(n) for almost every X∈ω². The proof of this result uses an improvement of Chaitin's counting theorem—we give a tight upper bound on the number of strings σ∈n² such that K(σ)<n+K(n)−m.The work on upward oscillations has applications to the K-degrees. Write XK_?Y to mean that K(X?n)?K(Y?n)+O(1). The induced structure is called the K-degrees. We prove that there are comparable () 1-random K-degrees. We also prove that every lower cone and some upper cones in the 1-random K-degrees have size continuum.Finally, we show that it is independent of ZFC, even assuming that the Continuum Hypothesis fails, whether all chains of 1-random K-degrees of size less than ℵ₀² have a lower bound in the 1-random K-degrees.     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

Kolmogorov complexity and computably enumerable sets

We study the computably enumerable sets in terms of the:     

Dimension spectra of random subfractals of self-similar fractals

The dimension of a point x   in Euclidean space (meaning the constructive Hausdorff dimension of the singleton set {x}$\{x\}$) is the algorithmic information density of x  . Roughly speaking, this is the least real number dim(x)$\dim (x)$ such that r×dim(x)$r\times \dim (x)$ bits suffice to specify x   on a general-purpose computer with arbitrarily high precision 2^−r$2^{-r}$. The dimension spectrum of a set X   in Euclidean space is the subset of [0,n]$[0,n]$ consisting of the dimensions of all points in X.     

The $\mu$-measure as a tool for classifying computational complexity

Two simply typed term systems and are considered, both for representing algorithms computing primitive recursive functions. is based on primitive recursion, on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes for , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1n\ge 1\mathcal{R}^n_i$ denotes the \emph{th modified Heinermann class} based on . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by . By Ritchie's result, characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that characterises the polynomial time computable functions. Furthermore, the classes and coincide at and above level 2. Received: 22 September 1997 / Revised version: 12 May 1999     

On the computational complexity of cut-reduction

Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.     

Applications of matrix methods to the theory of lower bounds in computational complexity

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn ^(logn) for the function MINIMUM COVER using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.     

The strength of extensionality II — Weak weak set theories without infinity

By obtaining several new results on Cook-style two-sorted bounded arithmetic, this paper measures the strengths of the axiom of extensionality and of other weak fundamental set-theoretic axioms in the absence of the axiom of infinity, following the author’s previous work [K. Sato, The strength of extensionality I — weak weak set theories with infinity, Annals of Pure and Applied Logic 157 (2009) 234-268] which measures them in the presence. These investigations provide a uniform framework in which three different kinds of reverse mathematics-Friedman-Simpson’s “orthodox” reverse mathematics, Cook’s bounded reverse mathematics and large cardinal theory-can be reformulated within one language so that we can compare them more directly.     

Characterizing Valiant's algebraic complexity classes

Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniques. In this paper we gather known results and new techniques under a unifying theme, namely the restrictions imposed upon the gates of the circuit, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and _VNPe${\mathrm{VNP}}_{\mathrm{e}}$ or the completeness of the Determinant for VQP, and new results such as a characterization of the classes VQP and VP (which we can also apply to the Boolean class LOGCFL) or a full answer to a conjecture in Bürgisser's book [Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, Berlin, 2000]. We also show that for circuits of polynomial depth and unbounded size these models all have the same expressive power and can be used to characterize a uniform version of VNP.     

Truth‐table Schnorr randomness and truth‐table reducible randomness

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth‐table Schnorr randomness (defined in 6 too only by martingales) and truth‐table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth‐table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth‐table Schnorr randomness. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Condition number based complexity estimate for solving polynomial systems

By modifying and combining algorithms in symbolic and numerical computation, we propose a real-root-counting based method for deciding the feasibility of systems of polynomial equations. Along with this method, we also use a modified Newton operator to efficiently approximate the real solutions when the systems are feasible. The complexity of our method can be measured by a number of arithmetic operations which is singly exponential in the number of variables.     

Condition number based complexity estimate for computing local extrema

In this paper, we present a new algorithm for computing local extrema by modifying and combining algorithms in symbolic and numerical computation. This new algorithm improves the classical steepest descent method that may not terminate, by combining a Sturm’s theorem based separation method and a sufficient condition on infeasibility. In addition, we incorporate a grid subdivision method into our algorithm to approximate all local extrema. The complexity of our algorithm is polynomial in a newly defined condition number, and singly exponential in the number of variables.