Advertisement
Published in:
2006 | OriginalPaper | Chapter
Kolmogorov Complexity with Error
Authors : Lance Fortnow, Troy Lee, Nikolai Vereshchagin
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We introduce the study of Kolmogorov complexity with error. For a metric
d
, we define
C
a
(
x
) to be the length of a shortest program
p
which prints a string
y
such that
d
(
x
,
y
) ≤
a
. We also study a conditional version of this measure
C
a
,
b
(
x
|
y
) where the task is, given a string
y
′ such that
d
(
y
,
y
′) ≤
b
, print a string
x
′ such that
d
(
x
,
x
′) ≤
a
. This definition admits both a uniform measure, where the
same
program should work given any
y
′ such that
d
(
y
,
y
′) ≤
b
, and a nonuniform measure, where we take the length of a program for the worst case
y
′. We study the relation of these measures in the case where
d
is Hamming distance, and show an example where the uniform measure is exponentially larger than the nonuniform one. We also show an example where symmetry of information does not hold for complexity with error under either notion of conditional complexity.