#

### CJTCS Special Issue: CATS 2009

### Selected papers from

# 2009 Computing: The Australasian Theory Symposium

### held in Wellington, New Zealand January 20-23 2009.

## Guest Editors: Rod Downey, Victoria University of Wellington, NZ

## Prabhu Manyem, Shanghai University, PRC.

#### Article 2010-4

Published by the Department of Computer Science, The University of Chicago.

####
On Process Complexity

Adam R. Day

School of Mathematics, Statistics and Operations Research

Victoria University of Wellington

PO Box 600, Wellington 6140

New Zealand

*June 22, 2010*
##### Abstract

Process complexity is one of the basic variants of Kolmogorov complexity.
Unlike plain Kolmogorov complexity, process complexity provides a simple
characterization of randomness for real numbers in terms of initial segment complexity.
Process complexity was first developed in [11]. Schnorr's
definition of a process, while simple, can be difficult to work with.
In many situations, a preferable definition of a process is that given in [9].
In this paper we define a variant of process complexity based on Levin and Zvonkin's
definition of a process. We call this variant strict process complexity.
Strict process complexity retains the main desirable properties of process complexity.
In particularl, it provides simple characterizations of Martin-Löf
random real numbers, and of computable real numbers. However, we will prove that
strict process complexity does not agree within an additive constant with Schnorr's
original process complexity.

One of the basic properties of prefix-free complexity is that it is subadditive.
Subadditive means that there is some constant *d* such that for all strings
*sigma*, *tau* the complexity of *sigma* *tau* (the concatenation
of the two strings) is less than or equal to the sum of the complexities of *sigma*
and *tau*
plus *d*. A fundamental question about any complexity measure is whether or not
it is subadditive. In this paper we resolve this question for process complexity by proving
that neither
of these process complexities is subadditive.

- The article:
**PDF** (192,218 bytes)
- Source material:
**ZIP** (47,884 bytes)
- Self citation in
**BIBTeX** (234 bytes)
- Original version (pre-June 2010):
**PDF** (159,437 byes)

2010, Article 3
2010, Article 5

Special Issue
Published articles