On Resource-Bounded Versions of the van Lambalgen Theorem

Abstrakt

The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequences A and B, B is Martin-Löf random and A is Martin-Löf random relative to B if and only if the interleaved sequence is Martin-Löf random.

This implies that A is relative random to B if and only if B is random relative to A. This paper studies the validity of this phenomenon for different notions of time-bounded relative randomness.

Klíčová slova

• van Lambalgen theorem
• relative randomness