Real quadratic Julia sets can have arbitrarily high complexity

Abstract: We show that there exist real parameters

c

for which the Julia set

J_{c}

of the quadratic map

z^{2} + c

has arbitrarily high computational complexity. More precisely, we show that for any given complexity threshold

T (n)

, there exist a real parameter

c

such that the computational complexity of computing

J_{c}

with

n

bits of precision is higher than

T (n)

. This is the first known class of real parameters with a non poly-time computable Julia set.

This page was built for publication: Real quadratic Julia sets can have arbitrarily high complexity