Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-139 | 2nd June 2017 15:03

Exact constructive and computable dimensions

RSS-Feed




Revision #1
Authors: Ludwig Staiger
Accepted on: 2nd June 2017 15:03
Downloads: 45
Keywords: 


Abstract:

In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension of (sets of) infinite strings. This
allows us to derive several bounds on the complexity functions of infinite
strings, that is, functions assigning to every finite prefix its Kolmogorov
complexity. In particular, it is shown that the exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.

Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.



Changes to previous version:

The references [Hit05], [HLM04], and [HLM08] were added:

Hitchcock's Theorem 4.4 [Hit05] was compared with Theorem 3 in Section 1.4.3.

In the introduction and Section 6 the connections of this work with the references on scaled dimension [HLM04], [HLM08] were briefly discussed.


Paper:

TR16-139 | 8th September 2016 18:38

Exact constructive and computable dimensions


Abstract:

In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension of (sets of) infinite strings. This
allows us to derive several bounds on the complexity functions of infinite
strings, that is, functions assigning to every finite prefix its Kolmogorov
complexity. In particular, it is shown that the exact Hausdorff dimension
of a set of infinite strings lower bounds the maximum complexity function
of strings in this set. Furthermore, we show a result bounding the exact
Hausdorff dimension of a set of strings having a certain computable
complexity function as upper bound.

Obviously, the Hausdorff dimension of a set of strings alone without any
computability constraints cannot yield upper bounds on the complexity of
strings in the set. If we require, however, the set of strings to be
$\Sigma_{2}$-definable several results upper bounding the complexity by the
exact Hausdorff dimension hold true. First we prove that for a
$\Sigma_{2}$-definable set with computable dimension function one can
construct a computable -- not only semi-computable -- martingale succeeding
on this set. Then, using this result, a tight upper bound on the prefix
complexity function for all strings in the set is obtained.



ISSN 1433-8092 | Imprint