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?^′.     

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.     

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^′.     

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.     

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.     

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     

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}$).     

Short propositional refutations for dense random 3CNF formulas

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notable are the exponential-size resolution refutation lower bounds for random 3CNF formulas with Ω(n^1.5−ε)$\mathrm{\Omega }(n^{1.5-\epsilon })$ clauses (Chvátal and Szemerédi [14], Ben-Sasson and Wigderson [10]). On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with Ω(n²/log?n)$\mathrm{\Omega }(n^2/\log ?n)$ clauses, shown by Beame et al. [6]. In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are TC⁰${\mathit{T}\mathit{C}}^0$ formulas (i.e., TC⁰${\mathit{T}\mathit{C}}^0$-Frege proofs) for random 3CNF formulas with n   variables and Ω(n^1.4)$\mathrm{\Omega }(n^{1.4})$ clauses.     

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.     

Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

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.     

Kolmogorov complexity and computably enumerable sets

We study the computably enumerable sets in terms of the:     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.