%
% Paper to Real Analysis Exchange
%
% (Feb.15th, 2001)
%
% "Computational Complexity of Fractal Sets"
%
%

\documentstyle{article}

%\topmargin -3.5cm
%\oddsidemargin 0cm

\newcommand\PP{{\rm P}}
\newcommand\NP{{\rm NP}}
\newcommand\NPcomp{{\rm NPcomp}}
\newcommand\NPhard{{\rm NPhard}}
\newcommand\NN{{\bf N}}
\newcommand\QQ{{\bf Q}}
\newcommand\RR{{\bf R}}
\newcommand\FF{{\cal F}}
\newcommand\noi\noindent
\newcommand\qed{\hfill$\Box$}
\newcommand\size{{\it size}}
\newcommand\encode[1]{\lceil{#1}\rceil}
\newcommand\bracket[1]{\langle{#1}\rangle}
\newcommand\pair{\mbox{\it pair}}
\newcommand\pleft{\mbox{\it left}}
\newcommand\pright{\mbox{\it right}}
\newcommand\bigfrac[2]{\begin{array}{c}{#1}\\\hline{#2}\end{array}}
\newcommand\eps\epsilon
\newcommand\bunsuu[2]{{}^{#1}\!/_{#2}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{prop}[definition]{Proposition}
\newtheorem{cor}[definition]{Corollary}
\newtheorem{exam}[definition]{Example}
\newtheorem{claim}[definition]{Claim}

\begin{document}

\noi
{\Large\bf Computational Complexity of Fractal Sets }

\ 

\noi
{\large Kamo Hiroyasu} \\
Faculty of Science, Nara Women's University \\
{\tt wd@ics.nara-wu.ac.jp}

\ 

\noi
{\large Kawamura Kiko} \\
Department of Mathematics, University of North Texas \\
{\tt kiko@unt.edu}

\ 

\noi
{\large Takeuti Izumi} \\
Graduate School of Informatics, Kyoto University \\
{\tt takeuti@kuis.kyoto-u.ac.jp}

	\begin{quote}
{\bf Abstract}

In studies on fractal geometry, it is important to determine 
whether the classification by means of
computational complexity is independent of the classification by
means of fractal dimension. 
In this paper, we show that each self-similar set
defined by polynominal time computable functions is
polynominal time computable, if the self-similar set satisfies 
a polynominal time open set condition. This fact provides us
examples of sets whose computational complexity are polynomial time computable, and which have non integer Hausdorff dimension. 
We also construct a set with computational complexity NP-complete and with an integer Hausdorff dimension.
These two examples establish the independence of
computational complexity and Hausdorff dimension.
	\end{quote}

\section{ Introduction }

\indent 

The aim of this paper is to find a mathematical tool other than
fractal dimension
to estimate the complexity in fractal geometry.

Although many of the traditional studies of fractal geometry have been
made by means of Hausdorff or other dimensions \cite{Falconer'85}, it is not
always easy to obtain the exact value of the dimension.
Many of the studies of fractal figures use self-similar sets, because they are
easy to define, to draw, and to calculate.

The box-counting method often appears in the manipulation of self-similar sets.
Consider a subset $A$ in the unit square $[0,1]^2$.
We partition $[0,1]^2$ into $2^n \times 2^n$ small squares called pixels
and paint each pixel $P_{i,j}$
obeying the rule that $P_{i,j}$ is black if $A \cap P_{i,j} \not= \O \empty$
and white otherwise.
Then we obtain an approximation of $A$.
By counting the number of black pixels for a large enough $n$,
we obtain a sufficient approximation of box-counting dimension on $A$.

In this paper, we consider both the efficiency of approximation and the time
of computation. Although the former has been investigated, e.g. \cite{Smith},
\cite{Morse}, the latter has never been studied.
This is the motivation for investigating
the time to compute an approximation of box-counting dimension
as one of the tools for estimation of complexity in fractal geometry.

Before investigating the time complexity, we must check the computability of
self-similar sets as the first step. From the point of view of Pour-El--Richards
style computable analysis \cite{Pour-El&Richards}, it is already known
that a self-similar set which is defined by computable contractions
is computable \cite{Kawamura&Kamo'98}, \cite{Kawamura&Kamo'97}.

In this paper, we investigate self-similar sets from the viewpoint of
computable analysis and propose computational complexity as one of the
tools for estimating the complexity of self-similar sets, other than Hausdorff dimension.

First, we recall computational complexity in analysis.
The definitions of computational complexity in this paper
are equivalent to those in \cite{Weihrauch'95}, \cite{Weihrauch'96} and known to be equivalent to those in \cite{Pour-El&Richards}.

Next, we provide a sufficient condition for a recursive self-similar set
to be in the computational complexity class P.
We obtain two theorems.

	\begin{theorem}
A self-similar set constructed by a set of polynomial time computable functions
is in the computational complexity class NP. 
	\end{theorem}

	\begin{theorem}
A self-similar set constructed by a set of polynomial time computable functions
is in the computational complexity class P, if the self-similar set satisfies
the polynomial time open set condition.  
	\end{theorem}

By using these theorems,
we can estimate the computational complexity of
most of the well-known self-similar sets.
For examples, the Koch curve is in the computational complexity class P,
and its Hausdorff dimension is \(\log 4/\log 3\), which is
a computable noninteger real number.

As a related work,
Ko \cite{Ko} constructed some figures with P
as its computational complexity and an uncomputable number as 
its Hausdorff dimension. He wasn't concerned with self-similar sets, and his 
figures were not self-similar sets.

Lastly, we give the following theorem to show
an example of NP-complete subsets of
the Euclidean plane. It is the image of a polynomial time
computable H\"older function. In addition, we prove that 
each H\"older polynomial time computable function is in the 
computational complexity class NP.
This example shows that the classification by means of
computational complexity does not coincide with the one
by means of Hausdorff dimension. 

	\begin{theorem}
There exists a closed set in the plane whose computational complexity is 
NP-complete, and the Hausdorff dimension is 1. 
	\end{theorem}

\setcounter{theorem}0

In this paper,
we use the notation {\NN} for the set of all the natural numbers \( \{0,1,2,...\} \),
{\QQ} for the set of all the rational numbers,
and {\RR} for the set of all the real numbers

\section{ Complexity of analytical objects } \label{ca}

We discuss the computational complexities of
real valued functions. The complexity of such a function is determined
by a standard encoding of rational numbers.
We have a polynomial time computable standard encoding.
First, we give the formal definition of polyominal time computability.
	\begin{definition}
Let \(f\) be a function from \(\NN^n\) to \(\NN\).
The function \(f\) is {\em polynominal time computable}
iff there exist a Turing machine \(M\) and \(k\in\NN\) such that
\(M\) returns the integer \(f(x_1,x_2,\dots,x_n)\) as the output
in time \(O((\log(x_1\cdot x_2\cdots
%\) \( \cdot % zzz
x_n))^k)\),
if an \(n\)-tuple of natural numbers \(\bracket{x_1,x_2,\dots,x_n}\) 
is given as the input. 
	\end{definition}
	\begin{definition}
The {\em standard encoding of rational numbers} is a one-to-one mapping
$ \QQ \mapsto \NN $, denoted $ q \mapsto \encode q $ satisfiying  the
following conditions. 
	\begin{enumerate}
	\item
There exists a polynominal time computable function \(f_1:\NN^2\to\NN\)
such that
for each positive integer $d$ and each integer $n \neq 0$,
the natural number $ \encode{n/d}=f_1(d,n) $.
	\item
There exists a polynominal time computable function \(f_2:\NN\to\NN\)
which satisfies the following:
for each natural number \(e\), it holds that
\( f_2(e)=0 \) iff there exists a rational number \( q \)
such that $ e = \encode{q} $.
	\item
There exist polynominal time computable functions \(f_3,f_4:\NN\to\NN\)
such that
for each natural number $e \neq 0$, if \(f_2(e)=0\) then
\(f_3(e)\neq0\) and \(e=\encode{f_4(e)/f_3(e)}\).
	\end{enumerate}
	\end{definition}
Such a encoding \(q\mapsto\encode q\) surely exists \cite{Weihrauch'87}.

We regard $ \encode q $ as the standard code of the rational number $q$. 
For $n\in\NN$, the size of \( n \) is written as 
$s=\size(n)\in\NN$, and is defined by $ 2^{s-1} \leq n < 2^n $ 
or $s=n=0$. For $q\in\QQ$, $\size(q)=\size(\encode{q})$.

Also we define {\em the standard encoding of pairing}
which is polynominal time computable.
	\begin{definition}
The {\em standard encoding of pairing} consists of three
polynominal time computable functions: $ \pair:\NN \times \NN \mapsto \NN $,  
$ \pleft:\NN \mapsto \NN $, and $ \pright:\NN \mapsto \NN$ such that 

{\center
$ n = \pair(\pleft(n),\pright(n)) $, \ 
$ m=\pleft(\pair(m,n)) $ \ and \ $ n=\pright(\pair(m,n)) $

\ }

\noi
for all natural numbers $m,n$.
	\end{definition}
We abbreviate $ \encode{\bracket{m,n}} $ for the \(\pair(m,n)\)
and call $ \encode{\bracket{m,n}} $ the code of the pair $ \bracket{m,n} $.
%\ % zzz
Similarly we abbreviate $ \encode{\bracket{l,m,n}} $ for $ \pair(l,\pair(m,n)) $,
and
call $ \encode{\bracket{l,m,n}} $ the code of the triple $ \bracket{l,m,n} $.
Recursively, we write $ \encode{\bracket {k,l,m,n}} $ for $ \pair(k, \pair(l,\pair(m,n)))$ and 
call $ \encode{\bracket{k,l,m,n}} $ the code of the quadruple $ \bracket{k,l,m,n} $.

We regard $ \encode{\bracket{ \encode{q_1}, \encode{q_2}, ..., \encode{q_n} }} $
as the encoding of an \(n\)-tuple of rational numbers
$ \bracket{ q_1, q_2, ..., q_n } $
and write simply $ \encode{\bracket{ q_1, q_2, ..., q_n }} $.

In general, we use the notation \(\encode x\) for denoting
the coding of a non-natural-number object \(x\).
That is, for a set \(X\neq\NN\), the map \(x\mapsto\encode x:X\to\NN\)
is a one-to-one function.
Thus, the code of \(\bracket{m,n}\in\NN^2\) is
\(\encode{\bracket{m,n}}=\pair(m,n)\in\NN\)
and the code of \(\bracket{q,r}\in\QQ^2\) is
\(\encode{\bracket{q,r}}=\pair(\encode q,\encode r)\in\NN\).

We write \(\PP_{\NN,\NN}\)
for the set of polynominal time computable functions over natural numbers.

	\begin{definition}
The set \( \PP_{\NN,\QQ} \) is the set of functions from {\NN} to {\QQ}
such that \( f \) is in \( \PP_{\NN,\QQ} \)
iff there is \( g \in \PP_{\NN,\NN} \)
such that $ \encode{ f(n) } = g(n) $ for all $n\in\NN$.

The set \( \PP_{\QQ,\NN} \) is the set of functions from {\QQ} to {\NN}
such that \( f \) is in \( \PP_{\QQ,\NN} \)
iff there is \( g \in \PP_{\NN,\NN} \)
such that $ f(q) = g(\encode{q}) $ for all $q\in\QQ$.

The set \( \PP_{\QQ,\QQ} \) is the set of functions of {\QQ} into {\QQ}
such that a function \( f \) is in \( \PP_{\QQ,\NN} \)
iff there is \( g \in \PP_{\NN,\NN} \)
such that $ \encode{f(q)} = g(\encode{q}) $ for all $q\in\QQ$.

A function \( f \in \PP_{\NN,\QQ} \)
or \( f \in \PP_{\QQ,\NN} \)
or \( f \in \PP_{\QQ,\QQ} \) is called
{\em polynominal time computable}.
	\end{definition}
Similarly we define the sets
\(\PP_{\QQ\times\NN,\QQ}\), \(\PP_{\QQ,\QQ\times\QQ}\), and so forth.
The sets \(\PP_{\QQ\times\NN,\QQ}\)
is a set of functions from \(\QQ\times\NN\) to \(\QQ\).

	\begin{exam}\rm
All of the following functions are in \(\PP_{\QQ\times\QQ,\QQ}\).
	\begin{enumerate}
	\item
addition: \((q,q')\mapsto q+q':\QQ\times\QQ\to\QQ\)
	\item
subtraction: \((q,q')\mapsto q-q':\QQ\times\QQ\to\QQ\)
	\item
multiplication: \((q,q')\mapsto q\cdot q':\QQ\times\QQ\to\QQ\)
	\item
division: \((q,q')\mapsto\left\{
\begin{array}{ll}
q'/q & ( q \neq 0 ) \\
0 & ( q = 0 )
\end{array}
\right.:\QQ\times\QQ\to\QQ\)
	\end{enumerate}
	\end{exam}
% Note that $\size(d)+\size(|n|)\leq O((\size(n/d))^k)$ for some $k$.

	\begin{definition}
The set \( \PP_\RR \) is a subset of \(\RR\) such that
\(r\in\PP_\RR\) iff there is a function \( q \in \PP_{\NN,\QQ} \) such that 
$ | q(k) - r | < 1/k $
for each positive integer $k$.

A real number $r\in\PP_\RR$ is called {\em polynominal time computable}.
	\end{definition}
This definition is equivalent to the condition that a real number $r$ belongs to $\PP_\RR$
iff there exists a Turing machine which computes its approximation
with $n$ significant digits in polynominal time of $n$
\cite{Weihrauch'87} \cite{Weihrauch'95} \cite{Weihrauch'96}.
	\begin{exam}\rm
All algebraic numbers, $\pi$, and $e$ are in \(\PP_\RR\).
	\end{exam}
Usually, the complexity of a real valued function is defined
by the run time of a Type-2 Machine \cite{Weihrauch'87},
or an oracle Turing machine \cite{Ko}.
In this paper we define complexity in another way.
We define the complexity of a real function
by using an ordinal Turing machine, not a Type-2 machine. 
However, these definitions are equivalent, that is,
the class of polynominal time computable real functions by our definition
is equal to the class of
polynominal time computable real functions by the traditional definition.
	\begin{definition}\label{prr}
We say a function \( f:\RR\to\RR \) is in \( \PP_{\RR,\RR} \)
iff there exist functions
$g \in\PP_{\QQ^2,\QQ}$ and $h \in\PP_{\QQ^2\times\NN,\QQ}$
such that the following hold. 
	\begin{enumerate}
	\item
For each rational number $x$ and each positive rational number $\eps>0$,
$g(x,\eps)$ is a rational number such that
\( | g(x,\eps) - f(x) | < \eps . \)
	\item
Let $x,l$ be arbitrary rational numbers and \(k\) be an arbitrary natural number.
Let \(z,z'\) be rational numbers which satisfy
\(z\in(x-l,x+l)\) and \(z'\in(x-l,x+l)\).
Suppose $ |z-z'| < h(x,l,k) $.
Then we have \( | f(z') - f(z) | < 1/k \).
	\end{enumerate}
A function \( f \in \PP_{\RR,\RR} \) is called
{\em polynominal time computable}.
	\end{definition}
Condition 1 of Definition \ref{prr} involves the modulus of approximation. 
Condition 2 involves the modulus of uniform continuity. 
Similary define the set \( \PP_{\RR^2,\RR^2} \).
The notation \( | (x,y)| \) stands for the absolute value, i.e, 
\( |(x,y)| = \sqrt{x^2+y^2} \),
and \( B((x,y),\rho) =  \left\{(x',y')\left|\rule{0em}{2.5ex}
\;|(x',y')-(x,y)|<\rho\right.\right\} \).
	\begin{definition}
The set \( \PP_{\RR^2,\RR^2} \) is a set of functions from \(\RR^2\) to \(\RR^2\)
such that a function \( f:\RR^2\to\RR^2 \) is in \( \PP_{\RR^2,\RR^2} \)
iff there exist functions
$g \in\PP_{\QQ^3,\QQ^2}$ and $h \in\PP_{\QQ^3,\QQ}$
such that the following hold. 
	\begin{enumerate}
	\item
For each $x\in\QQ^2$ and each rational number $\eps>0$,
$g(x,\eps)$ is in $ \QQ^2$ and    
\(
| g(x,\eps) - f(x) | < 1/\eps 
\).
	\item
Let $x$ be an arbitrary rational point \(\in\QQ^2\),
and \(\eps,\rho\) be arbitrary positive rational number.
Let \(z,z'\) be rational numbers satisfying \(z\in B(x,\rho)\) and \(z'\in B(x,\rho)\).
Suppose $| z-z' | < h(x,\rho,\eps)$.
Then we have \( | f(z') - f(z) | < \eps \).
	\end{enumerate}
	\end{definition}
The following propositions are easily shown.
	\begin{prop}
The set $\PP_{\RR}$ is closed under real functions in $\PP_{\RR,\RR}$.
	\end{prop}
	\begin{prop}
The set $\PP_{\RR,\RR}$ is closed under composition.
	\end{prop}


\section{ Computational complexity of figures } \label{cf}

We define the complexity of geometrical figures.
We regard geometrical figures as closed subsets of $ \RR^2 $.
The notation \( {\cal P}(X) \) stands for the power set of \( X \),
that is, \( E \in {\cal P}(X) \) iff \( E \subset X \).
	\begin{definition}
A {\em problem} is a subset of $ \NN$.
Let $P$ be a problem, that is, $ P \subset \NN $ and $n$ be a natural number.
If $n\in P$
then we say that {\em the answer of $ P $ for the instance $ n $ is `yes'}.
If $n \not\in P$
then we say that {\em the answer of $ P $ for the instance $ n $ is `no'}.
	\end{definition}
	\begin{definition}
The set \( \PP_{\cal P(\NN)} \) is a subset of \(\cal P(\NN) \)
such that a problem \( P \) is in \( \PP_{\cal P(\NN)} \)
iff there is \( f \in \PP_{\NN,\NN} \)
such that \( P = \{ n\in\NN \; | \; f(n)=0 \} \).
A problem \( P \in \PP_{\cal P(\RR)} \) is called
{\em polynominal time computable}.
	\end{definition}
	\begin{definition}
The set \( \NP_{\cal P(\NN)} \) is a subset of \(\cal P(\NN) \)
such that a problem \( P \) is in \( \NP_{\cal P(\NN)} \)
iff there is \( Q \in \PP_{\cal P(\NN)} \) and
\( f \in \PP_{\NN,\NN} \)
such that for each \( n \), \( n \in P \) iff
there is a number \( m \leq f(n) \)
such that \( \encode{\bracket{n,m}} \in P \). A problem \( P \in \NP_{\cal P(\NN)} \) is called
{\em nondeterministic polynominal time computable},
or \NP.
	\end{definition}
	\begin{definition}
For problems \( P \) and \( Q \), the relation \( P \leq_\PP Q \) holds
iff there is a function \( f \in \PP_{\NN,\NN} \) such that
\( P = f^{-1}(Q) \). When \( P \leq_\PP Q \), we say that
\( P \) is {\em polynominal time reducible} into \( Q \).
	\end{definition}
	\begin{definition}
The set \(\NPhard_{\cal P(\NN)}\) is a subset of \(\cal P(\NN)\) such that
a problem \( P \) is in \(\NPhard_{\cal P(\NN)}\) iff
for any \( Q \in \NP_{\cal P(\NN)} \), \( Q \leq_\PP P \).
The set \(\NPcomp_{\cal P(\NN)}\) is a subset of \(\cal P(\NN)\) such that
\(\NPcomp_{\cal P(\NN)}=\NP_{\cal P(\NN)}\cap\NPhard_{\cal P(\NN)}\). 
A problem \( P \in \NPhard_{\cal P(\NN)} \) is called {\em NP-hard}. 
A problem \( P \in \NPcomp_{\cal P(\NN)} \) is called {\em NP-complete}.
	\end{definition}

We characterize a closed set $X$ in a plane
by determining for given \(x\in\RR^2\)
whether \(X\) intersects \(B(x,\eps)\) for each \(\eps>0\).
This means the following.
Fix a point \(x\in\RR^2\) and a closed set \(X\subset\RR^2\).
Then, does it holds that \( X\cap B(x,\eps) \neq \O \) for 
each \(\eps>0\) ? If yes, then \(x\in X\). If no, then \(x\not\in X\).

Unfortunately, it is not computable whether $X \cap B(x,\eps) \neq \O $
in general. However, for some $X$, it may be computable whether $X$ intersects to $B(x,\eps)$
or is separated from $B(x,\eps/2)$. Therefore, we define the computable complexity of closed sets as follows.  
	\begin{definition}\label{defdist}
For a point \( x \in \RR^2 \) and a set \( X \subset \RR^2 \),
the notation \( d(x,X) \) stands for the distance between \( x \) and \( X \),
which is defined as:
\[
d(x,X) =\inf_{x'\in X} |x'-x| \qquad ( X \neq \O ),
\qquad d(x,\O) = \infty .
\]
	\end{definition}
We write \( \FF(\RR^2) \) for the set of all closed sets in \( \RR^2 \).
	\begin{definition}
Let $P$ be a problem, that is, $ P \subset \NN $ and let  $ X $ be a closed set in $ \FF(\RR^2) $.
We say \( P \vdash X \) iff the following conditions hold.
	\begin{enumerate}
	\item
If $ \encode{\bracket{ x, y, \eps }} \in P$ then
$ X \cap B( ( x, y ), 2\eps) \neq \O $.
That is, $d((x,y),X)<2\eps$.
	\item
If $ \encode{\bracket{ x, y, \eps }} \not\in P$ then
$ X \cap B( ( x, y ), \eps) = \O $.
That is, $d((x,y),X)>\eps$.
	\end{enumerate}
% Let $C$ be a class of problems, that is, a subset of $\cal P(\NN)$.
% A closed set $X\subset\RR^2$ is in {\em complexity} of $C$ iff
% there is a problem $P\in C$ such that $P$ determines $X$.
We say that \( P \) {\em determines} \( X \) iff \( P \vdash X \).
	\end{definition}
This definition is equivalent to the definition in \cite{Weihrauch'87}.
	\begin{prop}
For a problem \( P \) and closed sets \( X, X' \subset \FF(\RR^2) \),
if \( P \vdash X \) and \( P \vdash X' \), then \( X = X' \).
	\end{prop}
	\begin{definition}
The set \( \PP_{\FF(\RR^2)} \) is a subset of \(\FF(\RR^2) \)
such that a closed set \( X \) is in \( \PP_{\FF(\RR^2)} \)
iff there exists \( P \in \PP_{\cal P(\NN)} \)
such that \( P \vdash X \). A closed set \( X \in \PP_{\FF(\RR^2)} \) is called
{\em polynominal time computable}.
	\end{definition}
	\begin{definition}
The set \( \NP_{\FF(\RR^2)} \) is a subset of \(\FF(\RR^2) \)
such that a closed set \( X \) is in \( \NP_{\FF(\RR^2)} \)
iff there exists \( P \in \NP_{\cal P(\NN)} \)
such that \( P \vdash X \). A closed set \( X \in \NP_{\FF(\RR^2)} \) is called
{\em nondeterministic polynominal time computable},
or \NP.
	\end{definition}
	\begin{definition}
The set \( \NPhard_{\FF(\RR^2)} \) is a subset of \(\FF(\RR^2) \)
such that a closed set \( X \) is in \( \NP_{\FF(\RR^2)} \)
iff for any problem \( P \), if \( P \vdash X \)
then \( P \in \NPhard_{\cal P(\NN)} \).
The set \(\NPcomp_{\FF(\RR^2)}\) is a subset of \(\FF(\RR^2)\) such that
\(\NPcomp_{\FF(\RR^2)}=\NP_{\FF(\RR^2)}\cap\NPhard_{\FF(\RR^2)}\). A closed set \( X \in \NPhard_{\FF(\RR^2)} \) is called {\em NP-hard}.
A closed set \( X \in \NPcomp_{\FF(\RR^2)} \) is called {\em NP-complete}.
	\end{definition}
	\begin{lemma}\label{nphard}
For a closed set \( X \in \FF(\RR^2) \),
\( X \in \NPhard_{\FF(\RR^2)} \)
iff there exists an NP-hard problem \( P \)
and a polynominal time computable function \( f \) of \( \NN \) into \( \NN \)
which satisfies the following conditions. 
	\begin{enumerate}
	\item
For each \( n \in f(\NN) \), there are rational numbers \(x,y\)
and a positive rational number \( \eps \)
such that $ n = \encode{\bracket{ x, y, \eps }} $.
	\item
If $ \encode{\bracket{ x, y, \eps }} \in f(P) $,
then $d((x,y),X)\leq\eps$.
	\item
If $ \encode{\bracket{ x, y, \eps }} \in f(\NN-P) $,
then $d((x,y),X)\geq2\eps$.
	\end{enumerate}
	\end{lemma}
	{\bf Proof.}
Suppose that \( Q \) is a problem and \( Q \vdash X \).
Then we show \( P \leq_\PP Q \), and therefore 
\( Q \in \NPhard_{\cal P(\NN)} \).

If \( n \in P \), then there is a triple \((x,y,\eps)\)
such that $ f(n) = \encode{\bracket{ x, y, \eps }} $
and $d((x,y),X)\leq\eps$.
By the definition of \( Q \vdash X \), we have \( f(n) \in Q \).
On the other hand, if \( n \not\in P \),
then there is a triple \((x,y,\eps)\)
such that $ f(n) = \encode{\bracket{ x, y, \eps }} $
and $d((x,y),X)\geq2\eps$.
By the definition of \( Q \vdash X \),
we have \( f(n) \not\in Q \). Therefore \( P = f^{-1}(Q) \).
	\qed
	\begin{exam}\rm
Let $l,m,n$ be integers, not all of which are zero.
Then a line $ lx+my=n $ is polynominal time computable.
The reason is as follows.
For each rational point $(x_2/x_1,y_2/y_1)$,
the distance $d$ between the point and the line is
calculated as:
	\[
d = \sqrt{ \bigfrac{
| \; l\cdot\bunsuu{x_2}{x_1}+m\cdot\bunsuu{y_2}{y_1} +n \; |
}{l^2+m^2} } \ .
	\]
Then, it is polynominal time computable to determine 
whether $ d \geq \eps $ or $ d < \eps $,
since this is equivalent to determine 
whether $ d^2 \geq \eps^2 $, and this requires
only the comparison of fractions.
We can make the computation
in polynominal time of \( \size(x)+\size(y)+\size(\eps) \).
	\end{exam}


\section{ Self-similar sets } \label{ss}

In this section, we discuss the complexities of self-similar sets.
We begin with some preliminaries on contractions and Hausdorff metric. 
	\begin{definition}
Let $(V,d)$ be a metric space.
A function $ \phi $ over $ V $ is a {\em contraction}
iff there is a real number $ \alpha < 1 $ such that
for any points $ x, y \in V $,
$ d( \phi(x), \phi(y) ) \leq \alpha d(x,y) $.
We also say that $\phi$ is a
{\em contraction with an upper bound of magnification $\alpha<1$}.
	\end{definition}
	\begin{definition}
We define the Hausdorff metric 
between $ x \in V $ and $ X \subset V $,
and between sets $ X \subset V $ and $ Y \subset V $.
	\[
d(x,X) = \inf_{y\in X}d(x,y)
, \quad
d(X,Y) =
\max \left\{ \; \inf_{x'\in X}d(x',Y), \; \inf_{y'\in Y}d(y',X) \; \right\} .
	\]
For the empty set, $ d(x,\O)=\infty $.
If either $ X $ or $ Y $ is empty, then $ d(X,Y)=\infty $.
	\end{definition}
When \( V = \RR^2 \), this definition of \( d(x,X) \) is identical to
Definition \ref{defdist}.
Note that for compact sets $X,Y$, if $d(X,Y)=0$ then $X=Y$.
For a contraction $\phi$ with an upper bound of magnification $\alpha<1$,
we have $ d(\phi(X),\phi(Y)) \leq \alpha d(X,Y) $.
	\begin{definition}
A {\em self-similar set} is a compact non-empty subset $ X \subset V $
which satisfies the following set equation
for contractions $ \phi_1, \phi_2, \dots, \phi_n $.
	\[
X = \bigcup^n_{i=1} \phi_i ( X ) .
	\]
We call the sequence of the contractions $ \phi_1, \phi_2, \dots, \phi_n $
a {\em self-similar system}.
If a compact non-empty subset $ X \subset V $
satisfies this equation, then we say that
$ X $ is a {\em self-similar set defined by
the self-similar system $ \phi_1, \phi_2, \dots, \phi_n $}.
	\end{definition}
The fundamental properties of self-similar sets were studied
by Hutchinson, Hata and others \cite{Hata}, \cite{Hutchinson}.
One of the most important properties is the following lemma.  
	\begin{lemma}\label{hata}
Suppose that the metric space \(V\) is complete.
Then for each sequence of contractions
$ \{ \phi_1, \phi_2, \dots, \phi_n \} $,
there exists exactly one self-similar set
defined by $ \phi_1, \phi_2, \dots, \phi_n $.
	\end{lemma}
	{\bf Proof.}
We provide a proof including their proof for completeness and for our notations.

First we show the construction of the self-similar set.
The proof of uniqueness follows the construction immediately.

Let $ \sigma $ be the set $ \{ 1, 2, \dots, n \} $.
Then $ \sigma^l $ denotes a set of $l$-tuples of elements in $ \sigma $,
that is,
$ \sigma^l =
\{ \bracket{ i_1, i_2, \dots, i_l } | \;
i_k \in \sigma \mbox{ for each } k \; \} $,
and $ \sigma^\omega $ denotes a set of infinite sequences
of elements in $ \sigma $, that is,
$ \sigma^\omega =
\{ \bracket{ i_1, i_2, \dots, i_k, \dots } | \;
i_k \in \sigma \mbox{ for each } k \; \} $.
For $ \bracket{i_1, i_2, \dots, i_l} \in \sigma^l $,
a function
$ \phi_{\bracket{i_1, i_2, \dots, i_l}} $ is defined as
	\[
\phi_{\bracket{i_1, i_2, \dots, i_l}} (x) =
\phi_{i_1}(\phi_{i_2}(\dots(\phi_{i_l}(x))\dots)) .
	\]
For $ \bracket{i_1, i_2, \dots} \in \sigma^l $,
a function
$ \phi_{\bracket{i_1, i_2, \dots}} $ is defined as
	\[
\phi_{\bracket{i_1, i_2, \dots}} (x) =
\lim_{l\to\infty}\phi_{\bracket{i_1, i_2, \dots, i_l}} (x) .
	\]
For any $ \bracket{i_1, i_2, \dots} \in \sigma^\omega $,
the limit in the definition of $ \phi_{\bracket{i_1, i_2, \dots}} $
always exists. That is because of the following inequalities.
Let $ L $ be the maximum of
$ d(x,\phi_1(x)), d(x,\phi_2(x)), \dots, d(x,\phi_n(x)) $.
Then this inequation holds:
	\[
d(\;x,\;\phi_{i_l}(x)\;)\leq L .
	\]
By applying $\phi_{i_{l-1}}$,
	\[
d(\;\phi_{i_{l-1}}(x),\;\phi_{\bracket{i_{l-1},i_l}}(x)\;)\leq \alpha L .
	\]
By applying $\phi_{i_{l-2}}$ again,
	\[
d(\;\phi_{\bracket{i_{l-2},i_{l-1}}}(x),\;
\phi_{\bracket{i_{l-2},i_{l-1},i_l}}(x)\;)\leq \alpha^2 L .
	\]
After iteration, finally we get:
	\[
d(\;\phi_{\bracket{i_1, i_2,\dots,i_{l-1}}}(x),\;
\phi_{\bracket{i_1, i_2,\dots,i_l}}(x)\;)\leq \alpha^{l-1} L .
	\]
Therefore, the sequence $ \phi_{\bracket{i_1, i_2,\dots,i_l}}(x) $ converges.
Moreover we get the following inequality:
	\[
d(\;
\phi_{\bracket{i_1, i_2,\dots,i_l}}(x),\;
\phi_{\bracket{i_1, i_2,\dots,i_l,i_{l+1},\dots}}(x)
\;)\leq \alpha^l L/1-\alpha .
	\]
Note that $ \phi_{\bracket{i_1, i_2,\dots}}(x) $ does not depends on $x$,
because
	\[
d(\; \phi_{\bracket{i_1, i_2,\dots}}(x),\;
\phi_{\bracket{i_1, i_2,\dots}}(y) \;) \leq
\alpha^\infty d(x,y) = 0.
	\]
Now we put $ X $ as the closure of
$ \{ \phi_{\bracket{i_1, i_2,\dots}}(x_0) | \;
\bracket{i_1, i_2,\dots} \in \sigma^\omega \; \} $
for a point $ x_0 $.
Actually, the set
$ \{ \phi_{\bracket{i_1, i_2,\dots}}(x_0) | \;
\bracket{i_1, i_2,\dots} \in \sigma^\omega \; \} $
is compact.
Note that $ X $ is defined independently of $ x_0 $.
It is obvious that the set $ X $ defined above satisfies the set equation
	\[
X = \bigcup^n_{i=1} \phi_i ( X ) .
	\]
Moreover, if another closed bounded set $ X' $ also satisfies this set equation,
then $ X=X' $,
because $ d(X,X') \leq d(\phi_i(X),\phi_i(X')) \leq \alpha\cdot d(X,X') $,
thus $ d(X,X')
=0 $.
\qed

\noi
We define sets $ X_l \subset V $ for natural numbers $ l $ as
\[ X_l = \{ \phi_{\bracket{i_1, i_2,\dots,i_l}}(x_0) | \;
\bracket{i_1, i_2,\dots,i_l}
\in \sigma^l \; \} . \]
These $ X_l $'s depend on $ x_0 $.
Each \( X_l \) is an approximation of \( X \)
with the estimated error.
We can easily see that $ d(X,X_l) \leq \alpha^lL/(1-\alpha) $. 

The following proposition is easily proved.  
	\begin{prop}
For a self-similar set $ X = \bigcup \phi_i ( X ) \; ( 1 \leq i \leq n ) $,
the Hausdorff dimension of $X$ is $ \leq -\log n /\log\alpha$.
	\end{prop}

We have defined contractions and self-similar sets
in a general complete metric space $V$.
Hereafter we discuss only the case where $ V = \RR^2 $, the Euclidean plane, 
and contractions which are functions from $ \RR^2 $ to $ \RR^2 $.
We regard closed sets as figures on $ \RR^2 $. 

The notion of computational complexity does not appear
in the definition of self-similar sets.
Now we define the notion of a self-similar system with complexity. 
	\begin{definition}
\ % zzz
A self-similar system $ ( \phi_1,\phi_2,\dots, \phi_n ) $
is called {\em polynominal time computable},
or a {\em \PP-self-similar system},
iff all of $ \phi_i $'s are in \(\PP_{\RR^2,\RR^2}\).
	\end{definition}
	\begin{prop}
If all of $ \phi_1, \phi_2, \dots, \phi_n \in \PP_{\RR^2,\RR^2} $ are
contractions,
then each $ \phi_{\bracket{i_1, i_2, \dots, i_l}} $
is also in \(\PP_{\RR^2,\RR^2}\).
Moreover, an approximation of $ \phi_{\bracket{i_1, i_2, \dots, i_l}}(x) $
within an error less than $ 1/2^m $ is computable in
polynominal time of $l+m+\size(x)$
for each rational point \( x \).
	\end{prop}
	{\bf Proof.}
Let \( f_i \) be an approximation to \( \phi_i \)
such that \( |\phi_i(x,\eps)-f_i(x,\eps)|<\eps \) for each \( i \).
There is an integer \( k \) such that
\( f_i(x.\eps) \) is computable in the time \( O((\size(x)+\size(\eps))^k) \),
for all \( i \),
because each \( \phi_i \) is in \( \PP_{\QQ^3,\QQ^2} \).
Moreover we assume that \( \encode{n/d} \) is computable
in the time \( O((\size(d)+\size(n))^k) \).

We will calculate the approximation of
\( \phi_{\bracket{i_1, i_2, \dots, i_l}} (x) \)
in several steps with auxiliary variables \( y_1, y_2, \dots, y_l \).
We will calculate \(y_s\) in Step \(s\) for \(1\leq s\leq l\) recursively.

\noi{\bf Step 1.}
In this step we will calculate \(y_1\).
For any $l, m$, we calculate \( \encode{\bunsuu1{l\cdot2^m}} \),
which is computable in time
\( O((\size(l\cdot2^m))^k) \leq O((m\cdot\log l)^k) \).
Therefore
\( \size(\bunsuu1{l\cdot2^m}) \leq O((m\cdot\log l)^k) \).
Then we calculate \( y_1 = f_{i_l}(x,\bunsuu1{l\cdot2^m}) \).
which is computable in time
\( O((\size(x)+\size(\bunsuu1{l\cdot2^m}))^k) \leq O((\size(x)+l\cdot\log m)^{k^2}) \).
It holds that \( |y_1-\phi_{i_l}|\leq\bunsuu1{l\cdot 2^m} \).
Note that \( \size(y_1) \leq
O((\size(x)+\size(l\cdot2^m))^k) \leq O((\size(x)+l\cdot\log m)^k) \),
because \( y_1 \) is as large as \( x \),
and the precision of \( y_1 \) is \( \bunsuu1{l\cdot2^m} \).

\noi{\bf\boldmath Step s.} \(( 2 \leq s \leq l )\).
In this step, the variables $y_1, y_2, \cdots , y_{s-1}$ have been calculated.
Now we calculate \(y_s\).

\[
\size(y_{s-1}) \leq
O\left((\size(x)+\size(l\cdot2^m))^k\right)
\leq
O\left((\size(x)+l\cdot\log m)^k\right) ,
\]
\[
|y_1-\phi_{\bracket{i_{l-s+2},i_{l-s+3},\dots,i_l}}(x)|
<\bigfrac{s-1}{\ l\cdot 2^m\!\!} .
\]
Then, we calculate \( y_s = f_{i_{l-s+1}}(y_{s-1},\bunsuu1{l\cdot 2^m}) \),
which is computable in time
\[
\begin{array}l
O((\size(y_{s-1})+\size(l\cdot2^m))^{k^2})
\\
\leq O((\size(x)+2\size(l\cdot2^m))^{k^2}) \leq O((\size(x)+l\cdot m)^{k^2}) .
\end{array}
\]
\noi
Then it holds that
\[
|y_s-\phi_{\bracket{i_{l-s+1}, i_{l-s+2}, \dots, i_l}}|
\leq \bigfrac{1}{\ l\cdot 2^m\!\!} .
\]
Note that \( \size(y_s) \) is also \( \leq
O(\size(x)+\size(l\cdot2^m)) \leq O(\size(x)+l\cdot m) \),
which is independent to \( s \).
That is because \(|y_s|\) is as large as \(|x|\)
and the precision of \( y_1 \) is \( \bunsuu1{l\cdot 2^m} \).

Finally, we obtain \( y_l \) which is
the approximation of \( \phi_{\vec i}(x) \) with error \( \leq 1/2^m \).
The total time of calculation is
\( \leq O((m\log l)+l\cdot(\size(x)+m\log l)^{k^2})
\leq O((l+m+size(x))^{2k+1}) \).
	\qed\vspace{1.5ex}\par\noi
Each $\phi_i$ is a contraction. This fact prohibits
the error of each step \( \phi_{i_k} \) from growing too big.
	\begin{theorem} \label{npself}
A self-similar set defined by a \PP-self-similar system
is in \(\NP_{\FF(\RR^2)}\).
	\end{theorem}
	{\bf Proof.}
For the given self-similar set $ X = \bigcup\phi_i(X) $ and a rational point $ x_0 $,
we construct the following NP problem. 
	\begin{quote}
For a given rational point $ x = (x_2/x_1,y_2/y_1) $
and a given small rational number $ \eps = e_2/e_1 > 0 $, determine whether 
there exists $l$ and $ \vec i \in \sigma^l$ satisfying 
$ \left| \overline{\phi_{\vec i}(x)} - x \right| < 3\eps/2 $,
where $ \overline{\phi_{\vec i}(x)} $ is the rational point
which is an approximation of $ \phi_{\vec i}(x) $
within an error $ < \eps/4 $,
and \( l \) is an integer such that
$ \alpha^2\eps/4 < \alpha^lL/(1-\alpha) < \eps/4 $
for $ L = \max \{ \; | \phi_i(x_0) - x_0 | \; \}_i $.
	\end{quote}
The integer $l$ can be calculated in the following manner:
any integer \( l \) such that 
\[
\bigfrac{\log((1-\alpha)\eps/4L)}{-\log\alpha} -2
<l<
\bigfrac{\log((1-\alpha)\eps/4L)}{-\log\alpha}
\]
will work. This is computable in polynominal time of
\( size(\eps)\leq O((size(e_1)+\size(e_2))^k \),
because \( \alpha \) and \( L \) are constant numbers.

First, we note that this problem is indeed an {\NP} problem, that is,
this question is computable in the polynominal time of
\(\size(x)+\size(\eps)\).
Then we will show the problem determines the self-similar set \( X \).

Put \( z = \overline{\phi_{\vec i}(x)} \).
If the $ \vec i $ above exists,
then \(|\phi_{\vec i}(x_0)-x|\leq|\phi_{\vec i}(x_0)-z|+|z-x|<7\eps/4\).
Hence the Hausdorff distance $ d(x,X_l) $ is less than $ 7\eps/4 $.
And $ d(X,X_l) < \alpha^lL/(1-\alpha) < \eps/4 $.
Therefore $ d(x,X) < 2\eps $.

To the contrary, suppose that there does not exist such \(\vec i\).
Then for each \(\vec i\), the distance is estimated as
\(|\phi_{\vec i}(x_0)-x|\geq|z-x|-|\phi_{\vec i}(x_0)-z|>5\eps/4\).
Thus $ d(x,X_l) > 5\eps/4 $.
Hence the Hausdorff distance is estimated as
$ d(x,X) \geq d(x,X_l)-d(X,X_l) > \eps $.

Thus this problem determines $X$.
	\qed\vspace{1.5ex}

Next, we give more precise estimations of computational complexity
for self-similar sets with some condition.
Instead of Theorem \ref{npself}, we know many
polynominal time computable self-similar sets defined by
\PP-self-similar systems. One of the most famous of them is the Koch curve.
We will give a sufficient condition for such self-similar sets.
	\begin{definition}
Let \( ( \phi_1,\phi_2,\dots,\phi_n ) \) be a self-similar system,
and \( X \) be a self-similar set such that $ X = \bigcup\phi_i(X) $.
Then the self-similar system \( ( \phi_1,\phi_2,\dots,\phi_n ) \)
satisfies the {\em open set condition} iff
there is an open set $ W $ such that
	\[
X \subset \overline W \ \ \mbox{ and } \ \ 
\phi_i ( W ) \cap \phi_j ( W ) = \O \mbox{ for } i \neq j .
	\]
	\end{definition}
The Koch curve is defined by a self-similar system
which satisfies the open set condition.
Yet, this open set condition is not sufficient
to determine the complexity of self-similar sets,
because the open set condition does not have the notion of complexity.
We have to give a stronger definition.
	\begin{definition} \label{defposc}
Let \( ( \phi_1,\phi_2,\dots,\phi_n ) \) be a self-similar system,
and \( X \) be a self-similar set such that $ X = \bigcup\phi_i(X) $.
The the self-similar system \( ( \phi_1,\phi_2,\dots,\phi_n ) \)
satisfies the {\em polynominal time open set condition},
or the {\em P-open-set condition}, iff
there exists an open set $ W $, a real number \( \alpha \in \PP_\RR \)
and functions
\( k \in \PP_{\QQ^3\times\NN^2,\NN} \) and
\( j \in \PP_{\QQ^3\times\NN^4,\NN} \) which satisfy the following:
	\begin{enumerate}
	\item
$ X \subset \overline W $.
	\item
$ \phi_i ( W ) \cap \phi_j ( W ) = \O $ for $ i \neq j $.
	\item
\( |\phi_i(y)-\phi_i(x)|\leq\alpha|y-x| \) \ for each
\( i \in \sigma \) and \( x,y \in \RR^2 \).
	\item
For each rational point $ x = (x_2/x_1,y_2/y_1) $,
each positive natural number $ c > 0 $,
a natural number $l$, and a sequence \( \vec j \in \sigma^l \),
$ B(x,\alpha^lc) \cap \phi_{\vec j} ( W ) \neq \O $, 
there is an integer \( i \) such that \( 0 \leq i < k(x,c,2^l) \)
and 
\[
\vec j = \left\langle
j(x,2^c,2^l,i,1), j(x,2^c,2^l,i,2), \dots, j(x,2^c,2^l,i,l)
\right\rangle
. \]
	\end{enumerate}
	\end{definition}
The last condition says that
we can list all the $ \vec i \in \sigma^l $
such that $ B(x,\eps) \cap \phi_{\vec i} ( W ) \neq \O $,
that is, $d(x,\phi_{\vec i}(W))<\eps$,
in polynominal time of \( \size(x)+\bunsuu1\eps+l \).
	\begin{theorem}\label{pss}
A \PP-self-similar set which satisfies the P-open-set condition is in
\(\PP_{\FF(\RR^2)}\).
	\end{theorem}
	{\bf Proof.}
In the NP problem in the proof of Theorem \ref{npself},
the possible choices of $ \vec i \in \sigma^l $ are listed in polynominal time
if we put \( c \) as a constant \( \geq \bunsuu{4L}{\alpha^2(1-\alpha)}\).
Therefore, we can check on all the possible choices in polynominal time.
	\qed\vspace{1.5ex}\par\noi
Most of the self-similar sets which have been well analysed
satisfy the P-open-set condition, hence they are in P. 
Then the following question arises. 
	\begin{itemize}
 		\item Question: Is there a P-self-similar set in \(\NP_{\FF(\RR^2)}-\PP_{\FF(\RR^2)}\), 
when we assume P $\neq$ NP ? 
	\end{itemize}

The answer has not been obtained yet; however, in the next section, 
we will construct an NP complete set, although it is not self-similar.

As the next lemma shows, Theorem \ref{pss} is useful enough,
because many well known self-similar sets satisfy the P-open-set condition. 

	\begin{lemma}
Let \((\phi_1,\phi_2,\dots,\phi_n)\) be a \PP-self-similar system consisting 
similar maps of common magnification \( \alpha \), satisfying the open set condition.
Then, it satisfies the \PP-open-set condition.
	\end{lemma}
	{\bf Proof.}
First we note that \(\alpha\in\PP_\RR\),
because \( \alpha \) is the common magnification of \( \phi_i \)'s,
which are in \(\PP_{\RR^2,\RR^2}\).

Let \( X \) be the self-similar set defined by \((\phi_i)_i\),
and \(W\) the open set which appears in the statement of open set condition.
Let \( d \) be a positive rational number which is greater than or equal to
the diameter of \( \bar W \), that is,
\( d \geq
\sup\left\{\;|y-x|\;\left|\;x,y\in X\rule{0em}{2ex}\right.\right\} \).
%This \( d \) is obtained as in the proof of Lemma \ref{hata}.
Let \(a\) be a positive rational number which is less than or equal to
the area of \(W\).
Let \( x_0 \) be a rational point in \(W\).
This point \( x_0 \) plays the role of \( x_0 \)
in the proof of Lemma \ref{hata}.
Fix a rational number \( \eps \) such that
\( \alpha^l c/2 \leq \eps \leq \alpha^l c \),
where \( \alpha^l c \) is as in Definition \ref{defposc}.
Note that \( \size(\eps) \leq O((l+\size(c))^h) \) for some \( h \),
because \( \alpha \) is a constant.

We construct functions \(j\) and \(k\)
which list the possible choices of \(i\).
Let \( K \) be an integer such that \( K \geq n \) and
\( K \geq \pi(4c+7d)^2/a \).
The function \(k(x,c,m)\) is a function
whose value is \( K \),
which depends only on \( c \) and is independent of \( x \) and \( m \).
It is obvious that \( k \in \PP_{\QQ^3\times\NN,\NN} \).

Let \( f_i \) be a function in \( \PP_{\QQ^3,\QQ^2} \) such that
\( |\phi_i(x)-f_i(x,\delta)|<\delta \)
for each rational point \( x \) and positive rational number \( \delta \).
There is an integer \( h \) such that for each \( i \),
the value \( f_i(x,\delta) \) is computable in the time
\( O\left((\size(x)+\size(\delta))^h\right) \),
and \( \size(f_i(x,\delta)) \leq O\left((\size(x)+\size(\delta))^h\right) \),
because each \( \phi_i \) is polynominal time computable.
Now, we show the procedure for calculating \( j \).
The procesure consists of several steps.
In Step \(s\) for \(1\leq s\leq l\), we will recursively calculate
an approximation of \(\alpha^s\), written \(\overline\alpha^s\),
and a mapping \(j_s(m,t)\)
which maps
\((m,t)\in\{1,2,\dots,s\}\times\{1,2,\dots,k_s\}\)
into \(j_s(m,t)\in\{1,2,\dots,n\}\).
We will write \(\vec j_{s,t}\) as
\[
\vec j_{s,t} = \bracket{ j_s(1,t), j_s(2,t), \dots, j_s(s,t) }
\in \{1,2,\dots,n\}^s
\]

\noi{\bf\boldmath Step 1.}
First we calculate \(\overline\alpha\), 
which is an approximation of \( \alpha \) with error \( < \alpha/2l \),
and \( \overline\alpha < 1 \).
The calculation time is \( O((\size(l)^h)) \) for some \( h \),
because \( \alpha \) is constant and \( \alpha\in\PP_\RR \).

Next, for each \( i \) such that \( 1 \leq i \leq n \),
we calculate \( f_i(x_0,\eps/l) \). 
Each \( f_i \) is an approximation for \( \phi_i(x_0) \).
Thus we write \( \overline{\phi_i(x_0)} \) for \( f_i(x_0,\eps/l) \).
We put \( k_1 = n \) and
\( j_1(1,t)=t \) for \( 1 \leq t \leq k_1 \).
\vspace{1.5ex}

\noi{\bf\boldmath Step \(s\).} \( ( 2 \leq s \leq l ) \).
Assume we have calculated \( \overline\alpha^{s-1}, j_{s-1}(m,t) \) and
\( \overline{\phi_{\vec j_{s-1,t}}(x_0)} \)
for \( 1 \leq m \leq s-1, 1 \leq t \leq k_{s-1} \).
We write \(\vec j_{s-1,t}\) as
\[
\vec j_{s-1,t} = \bracket{ j_{s-1}(1,t), j_{s-1}(2,t), \dots, j_{s-1}(s-1,t) },
\]
As induction hypothesis, they satisfy the following:
\[
\left|\overline{\phi_{\vec j_{s-1,t}}(x_0)}-\phi_{\vec j_{s-1,t}}(x_0)\right|
< (s-1)\eps/l,
\]
% \[
% \left|\overline{\phi_{\vec j_{s-1,t}}(x_0)}-x\right|
% < \bigfrac{s-1}l (\eps+\eps') + \overline\alpha^{s-1} d
% \]
and, for each
\( \vec i = \bracket{ i_1, i_2, \dots, i_l } \in \sigma^l \),
there exists \( t \) such that
\( \vec j_{s-1,t} =
% \bracket{ i_{l-s+2}, i_{l-s+3}, \dots, i_l } % zzz
\langle i_{l-s+2}, \) \( i_{l-s+3}, \dots, i_l \rangle % zzz
\)
if \( |x-\phi_{\vec i}(x_0)|<\eps \). 

Now, we calculate \(\overline\alpha^s\), which is obtained from 
\(\overline\alpha\times\overline\alpha^{s-1}\).
Note that \(|\overline\alpha^s-\alpha^s|<s\eps/l\),
because \(|\overline\alpha-\alpha|<\eps/l\).
Next we calculate
\( f_i\left(\overline{\phi_{\vec j_{s-1,t}}(x_0)},\eps/l\right) \)
for each \( i \) and \( t \),
where \( 1 \leq i \leq n \) and \( 1 \leq t \leq k_{s-1} \).
We write \( \overline{\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)} \)
for \( f_i\left(\overline{\phi_{\vec j_{s-1,t}}(x_0)} \right) \).
Then it holds that
\[
\left|\overline{\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)}
-\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)\right|
<s\eps/l .
\]
Hence, there is an integer \( k_s \leq K \) such that
there are \( k_s \) pairs of \( (t,i) \) such that
\[
\left|\overline{\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)}-x\right|
< 3\eps+\overline\alpha^sd .
\]
Since
\[
\left|\overline{\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)}-x\right|
< 3\eps+4\overline\alpha^sd,
\]
we have 
\[
\left|\phi_{\bracket{i,\vec j_{s-1,t}}}(x_0)-x\right|
< \bigfrac{s\eps}l+3\eps+4\overline\alpha^sd
< 4\eps+6\alpha^sd
< \alpha^s(4c+6d) .
\]
On the other hand, we have \(x_0 \in W\). Thus
\[
\phi_{\bracket{i,\vec j_{s-1,t}}}(W) \subset
B(x, \alpha^s(4c+7d) ) .
\]
The number of pairs \((i,t)\) which satisfies the last inequality above is
\( \leq \pi(4c+7d)^2/a \leq K  \).
We enumerate such \( i \)'s and \( t \)'s as
\( i_1, i_2, \dots, i_{k_s} \) and \( t_1, t_2, \dots, t_{k_s} \).
Thus, we enumerate such \( (t,i) \)'s as
\( (t_1,i_1), (t_2,i_2), \dots, (t_{k_s},i_{k_s}) \).
We define \( j_s(u,m) \) for \( 1 \leq m \leq s, 1 \leq u \leq k_s \) by 
\[
j_s(u,1)=i_u, \quad
j_s(u,m)=j_{s-1}(t_u,m+1) \quad ( m \leq s-1 ) .
\]
Put % \( \vec j_{s,u} \) as:
\(
\vec j_{s,u} = \bracket{ i_u, \vec j_{t_u,s-1} }
= \bracket{ j_s(u,1), j_s(u,2), \dots, j_s(u,s-1) }
\).

Note that for each
\( \vec i = \bracket{ i'_1, i'_2, \dots, i'_l } \in \sigma^l \),
if \( \phi_{\vec i}(W) \cap B(x,\alpha^lc) \neq \O \),
then there exists \( u \) such that
\( \vec j_{s,t_u} =
\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }. 
\)
This is because if \( \phi_{\vec i}(W) \cap B(x,\alpha^lc) \neq \O \),
then \( \phi_{\vec i}(W) \subset B(x,\alpha^lc+\alpha^ld) \),
and \( \phi_{\vec i}(X) \subset B(x,\alpha^lc+\alpha^ld) \),
therefore
\[
\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(W)
\subset B(x,\alpha^lc+\alpha^ld+\alpha^sd)
. \]
We also have 
\[
\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(x_0)
\in
\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(W), 
\]
and
\[
\left|
\overline{\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(x_0)}
-\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(x_0)
\right|<s\eps/l .
\]
Therefore
\[
\left|
\overline{\phi_{\bracket{ i'_{l-s+1}, i'_{l-s+2}, \dots, i'_l }}(x_0)}
-x\right|<s\eps/l+\alpha^lc+\alpha^ld+\alpha^sd
<3\eps+2\alpha^sd
<3\eps+4\overline{\alpha}^sd. 
\]

\noi{\bf\boldmath Last step.}
In this step, we put \( j(x,2^c,2^l,s,t) = j_l(s,t) \) for \( 1 \leq t \leq k_l \),
and \( j(x,2^c,2^l,s,t) = 1 \) otherwise.
\vspace{1.5ex}

We have calculated \( \overline{\phi_{\vec j_{s,t}}(x_0)} \) for 
\( 1 \leq t \leq k_s \leq K \). 
The size of the value of each
\( \overline{\phi_{\vec j_{s,t}}(x_0)} \) is as large as
\( O\left((\size(x_0)+\size(\eps))^h\right) \),
because the precision of it is near \( \eps \),
that is, it has the error as large as \(O(\eps)\).
Therefore, \( j \) is a polynominal time computable function.
	\qed
	\begin{exam}\rm
The Koch curve satisfies our P-open-set condition.
	\end{exam}

\section{ The image of a function satisfying a H\"older condition } \label{holder}

In this section, we construct an NP complete set
which is defined as the image of a function satisfying a H\"older condition.
	\begin{definition}
Let $ V $ and $ W $ be metric spaces.
A function $f$ from $V$ to $W$ satisfies a {\em H\"older condition}
of index $\alpha$ iff there is a $ k $ such that for any $x,y\in V$,
	\[
d_W( \; f(x), \; f(y) \; ) < k(d_V(x,y))^\alpha .
	\] 
	\end{definition}
Functions satisfying a H\"older condition are continuous.
A H\"older condition of index 1 is equivalent to
Lipschitz continuity.
	\begin{prop}
Let $f$ be a function from $V$ to $W$ satisfying a H\"older condition
of index $\alpha$, and the Hausdorff dimension of $V$ is $D$.
Then the Hausdorff dimension of $f(V)$ is $ \leq D / \alpha $.
	\end{prop}
The proof is clear.

Hereafter, we write $ I $ for a unit interval $ [ 0, 1 ] $.
	\begin{definition}
The set \( \PP_{I,\RR} \) is the set of functions from \(I\) to {\RR}
such that \( f \) is in \( \PP_{I,\RR} \) iff there is \( g \in \PP_{\RR,\RR} \) and
\( \forall x\in I. f(x)=g(x) \).

The set \( \PP_{I,\RR^2} \) is the set of functions from \(I\) to \(\RR^2\)
such that \( f \) is in \( \PP_{I,\RR^2} \)
iff there is \( f_1, f_2 \in \PP_{I,\RR} \) and
\( f(x)=(f_1(x),f_2(x)) \).
	\end{definition}
	\begin{lemma}\label{npholder}
Let $ f $ be a function in $ \PP_{I,\RR^2} $
If $ f $ satisfies a H\"older condition of some index,
then $ f(I) $ is in \( \NP_{\FF(\RR^2)} \). 
	\end{lemma}
	{\bf Proof.}
If $ \vec i = \bracket{ i_1, i_2, \dots, i_l } \in \{ 0,1 \}^l $
is the bit sequence, then we write
$ 0.\vec i $ for the binary fraction $ 0.i_1i_2\dots i_l $.

Now we construct an NP problem such that:
	\begin{quote}
Let $ x = (x_2/x_1,y_2/y_1) $ and $ \eps = e_2/e_1 > 0 $ be given. The question is  
whether there exists some choice $ \vec i \in \sigma^l $
which satisfies $ | y - x | < 3\eps/4 $
where $ y $ is an approximation of $ f(0.\vec i) $
within an error $ < \eps/4 $,
and $ k/2^{\alpha l} < \eps/4 $.
	\end{quote}
If such an \(i\) exists, then the distance $ | y-x | $ is $ < 3\eps/4 $.
And $ d(y,f(I)) < \eps/4 $.
Therefore $ d(x,f(I)) < \eps $.
If not, then $ | y-x | \geq 3\eps/4 $.
Therefore $ d(x,f(I)) > \eps/2 $.
Thus this problem determines $ f(I) $.
	\qed\vspace{1.5ex}\par\noi
There exists the image of a function satisfying a H\"older condition in NP and not in P.
Indeed, it is in the complexity of NP complete. 
We construct such an orbit in the remaining part of this paper. 
Of course we assume P $\neq$ NP.

We take an NP complete problem $Q$ which consists of the following data:
	\begin{quote}
For a given instance $ \vec v \in \{ 0, 1 \}^l $ for some $ l $,
the question is whether there exists some guess $ \vec w \in \{ 0, 1 \}^l $
which satisfies $ q( \vec v, \vec w ) = 0 $,
where $ q $ is polynominal time computable function
of \( (\{0,1\}^*)^2 \) into \( \{0,1\} \).
	\end{quote}
In this problem $Q$, the lengths of an instance $v$
and the certificate $w$ for the instance $v$ are equal. 

Next we construct a function of $I$ into $ \RR^2 $
satisfying a H\"older condition such that the problem $Q$ is reduced to $ f(I) $. 
The function $ f $ consists of two functions $ f_1 $ and $ f_2 $ of $ I $ into $ \RR $
such that $ f(t) = (f_1(t),f_2(t)) $.

After we define $ f $, we will reduce the NP problem $Q$ into
a problem $P$ which determines $ f(I) $.
For this purpose, we define an encoding $c(\vec v,\vec w)$ which maps
binary sequences $ \vec v \in \bracket{ v_1,v_2,\dots,v_l } \in \{ 0, 1 \}^l $
and $ \vec w \in \bracket{ w_1,w_2,\dots,w_m } \in \{ 0, 1 \}^m $
to a quinary sequence
$ c(\vec v,\vec w) = \bracket{ c_1, c_2, \dots, c_{l+m+1} }
\in % zzz
\{ 0, 1, \dots, 4 \}^{l+m+1} $.
The encoding $c(\vec v,\vec w)$ is defined in the following manner.
	\begin{enumerate}
	\item
$ c_i = v_i + 2 $ for $ 1 \leq i \leq l $.
	\item
$ c_{l+1} = 1 $.
	\item
$ c_i = w_{i-l-1} + 2 $ for $ l+2 \leq i \leq l+m+1 $.
	\end{enumerate}
For example, $ c(\bracket{0},\bracket{1})=\bracket{213} $,
and $ c(\bracket{10},\bracket{110})=\bracket{321332} $.
Note that $ c(\vec v,\vec w) = \bracket{ c_1,\dots.c_{l+m+1} } $
consists of only 1, 2, and 3. It does not have 0 or 4.

We use the notations \( 0.\vec v \) and \( (0.\vec c)_5 \) as follows.
If $\vec v$ is a binary sequence, then $0.\vec v$ denotes
a binary fraction $ 0.v_1v_2\dots v_l = 2^{-1}v_1+2^{-2}v_2+\cdot+2^{-l}v_l $.
Similarly, if $ \vec c = \bracket{ c_1, c_2, \dots, c_n } $ is
a quinary sequence, then $ (0.\vec c)_5 $ denotes a quinary fraction
$ ( 0.c_1c_2\dots c_n )_5 = 5^{-1}c_1+5^{-2}c_2+\cdot+5^{-n}c_n $.

First we define $ f_1 $. Because $ f $ is continuous, so is $ f_1 $.
Therefore, it is sufficient to define the value of $ f_1(t) $
only for quinary fractions $t$.
Let $ t \in I $ be the $ t = (0.t_1t_2\dots t_n)_5 $,
where \( t_n \neq 0 \). Let $i$ be a smallest number such that 
$ t_i \in \{ 0, 4 \} $, that is, $ t_j \in \{ 1, 2, 3 \} $ for all $ j < i $. 
Then we make the case selection by using this $ i $.
		\begin{itemize}
		\item{\bf Case 1:}
If $ t = 1 $, that is, there does not exist a sequence $ \vec t $
such that $ t = (0.\vec t)_5 $,
then:

$ f_1(1) = 0 $.
		\item{\bf Case 2:}
If such a digit $ t_i $ does not exist,
that is, all of $ t_j $'s are 1, 2 or 3, then:
	\begin{itemize}
	\item{\bf Case 2.1:}
If there exist binary sequences $ \vec v $ and $ \vec w $ such that
$ q(\vec v, \vec w)=0 $ and
$ \bracket{ t_1, \dots, t_n } = c(\vec v, \vec w) $, then:

$ f_1(t) = 1/5^n $.
Note that $ n \geq 1 $ in this case.
	\item{\bf Case 2.2:}
Otherwise, $ f_1(t) = 0 $. This case includes $ t=0 $.
	\end{itemize}
		\item{\bf Case 3:}
If such a digit $ t_i $ exists, that is, $ i $ is a smallest number such that
$ t_i $ is 0 or 4, then:
	\begin{itemize}
	\item{\bf Case 3.1:}
If $ t_i = 0 $, then:

$ f_1(t) = (1-u)f_1(\,(0.t_1\dots t_{i-1})_5) $,
where $ u = (0.t_{i+1}\dots t_n)_5 $.
	\item{\bf Case 3.2:}
If $ t_i = 4 $, then:

$ f_1(t) = u\cdot f_1(\,(0.t_1\dots t_{i-2}(t_{i-1}+1))_5) $,
where $ u = (0.t_{i+1}\dots t_n)_5 $, for $i\geq2$.

If $ i=1 $,then $ f(t) = 0 $.
	\end{itemize}
		\end{itemize}
It is easy to observe that $ f_1 $ satisfies the Lipschitz condition, because 
$ | f_1(t')-f_1(t) | \leq | t'-t | . $
If the pair of $ \vec v $ and $ \vec w $ is
a valid pair of an instance and a guess,
that is, $q(\vec v,\vec w)=0$ holds,
then $f_1(t)$ behaves as the following graph near
$ t_0 = (0.c(\vec v,\vec w))_5 $.

\begin{center}
\begin{picture}(300,120)(-150,-20)
	\put(-150,0){\vector(1,0){300}}
	\put(0,-20){\vector(0,1){120}}
	\put(-60,0){\line(1,1){60}}
	\put(0,60){\line(1,-1){60}}
	\put(-60,-3){\line(0,1){6}}
	%\put(0,-3){\line(0,1){6}}
	\put(60,-3){\line(0,1){6}}
	\put(-3,60){\line(1,0){6}}
	\put(150,3){\makebox(0,0)[br]{$t$}}
	\put(3,100){\makebox(0,0)[tl]{$f_1(t)$}}
	\put(-60,-5){\makebox(0,0)[t]{$t_0-1/5^n$}}
	\put(3,-5){\makebox(0,0)[tl]{$t_0$}}
	\put(60,-5){\makebox(0,0)[t]{$t_0+1/5^n$}}
	\put(3,62){\makebox(0,0)[bl]{$1/5^n$}}
\end{picture}
\end{center}

Next we define $ f_2 $, which is similar to $f_1$.
		\begin{itemize}
		\item{\bf Case 1:}
If $ t = 1 $, that is, there does not exist a sequence $ \vec t $
such that $ t = (0.\vec t)_5 $, then:

$ f_2(1) = 0 $.
		\item{\bf Case 2:}
If such a digit $ t_i $ does not exist,
that is, all of $ t_j $'s are 1, 2 or 3, then:
	\begin{itemize}
	\item{\bf Case 2.1:}
If there exist binary sequences $ \vec v $ and $ \vec w $ such that
$ q(\vec v, \vec w)=0 $ and
$ \bracket{ t_1, \dots, t_n } = c(\vec v, \vec w) $, then:

$ f_2(t) = (0.\vec v)/5^n $.
Note that $ n \geq 1 $ in this case.
	\item{\bf Case 2.2:}
Otherwise, $ f_2(t) = 0 $. This case includes $ t=0 $.
	\end{itemize}
		\item{\bf Case 3:}
If such a digit $ t_i $ exists, that is, $ i $ is a smallest number such that
$ t_i $ is 0 or 4, then:
	\begin{itemize}
	\item{\bf Case 3.1:}
If $ t_i = 0 $, then:

$ f_2(t) = (1-u)f_2(\,(0.t_1\dots t_{i-1})_5) $,
where $ u = (0.t_{i+1}\dots t_n)_5 $.
	\item{\bf Case 3.2:}
If $ t_i = 4 $, then:

$ f_2(t) = uf_2(\,(0.t_1\dots t_{i-2}(t_{i-1}+1))_5) $,
where $ u = (0.t_{i+1}\dots t_n)_5 $, for $ i\geq 2 $.

If $ i=1 $,then $ f(t) = 0 $.
	\end{itemize}
		\end{itemize}
Let $ t_0 $ be $ (0.c(\vec v,\vec w))_5 $,
and $ l $ be the length of $ \vec v, $.
Here the length of $c(\vec v,\vec w)$ is $ 2l+1 $.
If the pair of $ \vec v $ and $ \vec w $ is
a valid pair of an instance and a guess,
that is, $q(\vec v,\vec w)=0$ holds,
then the part of the orbit $f([t_0-1/5^{2l+2},t_0+1/5^{2l+2}])$
draws the following segment.

\begin{center}
\begin{picture}(200,120)(-50,-20)
	\put(-50,0){\vector(1,0){200}}
	\put(0,-20){\vector(0,1){120}}
	\put(0,0){\line(5,3){100}}
	\put(0,0){\dashbox{5}(100,60){}}
	\put(100,-3){\line(0,1){6}}
	\put(-3,60){\line(1,0){6}}
	\put(0,0){\makebox(-2,-2)[tr]{$O$}}
	\put(150,-3){\makebox(0,0)[tr]{$f_1(t)$}}
	\put(-3,100){\makebox(0,0)[tr]{$f_2(t)$}}
	\put(100,-5){\makebox(0,0)[t]{$1/5^{2l+2}$}}
	\put(-3,60){\makebox(0,0)[r]{$(0.\vec v)/5^{2l+2}$}}
	\put(102,60){\makebox(0,0)[l]{$(1/5^{2l+2},(0.\vec v)/5^{2l+2})$}}
\end{picture}
\end{center}

It is clear that $f(I)$ is the union of such segments for all $\vec v$'s
which have their own certificates. 

	\begin{theorem}
There is a function $f$ in $\PP_{I,\RR^2}$, which satisfies the Lipschitz continuity, 
and whose image $f(I)$ is in \(\NPcomp_{\FF(\RR^2)}\).
	\end{theorem}
	{\bf Proof.}
We show the function \( f \) defined as above satisfies
the statement of this theorem.

It is obvious that \( f \in \PP_{I,\RR^2} \).
By Lemma \ref{npholder}, \( f(I) \in \NP_{\FF(\RR^2)} \).

Next we will show that \( f(I) \in \NPhard_{\FF(\RR^2)} \).
In order to show that, we need to find a function \( g \)
of \( \{0,1\}^* \) into \( \RR \) which satisfies the condition in
Lemma \ref{nphard}.
We are identifying \( \{0,1\}^* \) with {\NN}
by the standard isomorphism \( \{0,1\}^* \cong \NN \).

Remember that the problem \( Q \) is defined as follows.
For an instance \( \vec v \in \{0,1\}^* \), \( \vec v \in Q \)
iff there is some \( \vec w \in \{0,1\}^* \)
of the same length as \( \vec v \) such that \( q(\vec v,\vec,w)=0 \).

We define \( g \) as
\( g(\vec v)=\encode{\bracket{1/5^{2l+2},(0,\vec v)/5^{2l+2},1/5^{3l+3}}} \),
where \( l \) is the length of \( \vec v \).
It is certain that \( g \) is in \( \PP \).
Note that \( g \) is an one-to-one map.

If \( f(\vec v) \in f(Q) \), that is, \( \vec v \in Q \),
then there is some $\vec w$ such that $q(\vec v,\vec w)=0$.
Let a point $p$ be 
where $l$ is a length of $\vec v$.
Then $ f(I) $ passes through the point
$(1/5^{2l+2},
(0.\vec v)/5^{2l+2})$.
Hence \(d(\;(1/5^{2l+2},(0.\vec v)/5^{2l+2}),f(I)\;)=0\).

On the other hand, if \( f(\vec v) \in f(\NN-Q) \),
that is \( \vec v \in Q \),
then there is no $\vec w$ such that $q(\vec v,\vec w)=0$.
%Let a point $p$ be $(1/5^{2l+2},(0.\vec v)/5^{2l+2})$,
%where $l$ is a length of $\vec v$.
Then $ f(I) $ does not have a segment whose inclination is
$ 0.\vec v $. Therefore, $ f(I) $ does not pass through the point
$(1/5^{2l+2},(0.\vec v)/5^{2l+2})$.
The nearest segments to this point is
the segment through the point
\( (1/5^{2l+2},
% \) \( % zzz
(0.\vec v-1/5^l)/5^{2l+2}) \)
and the segment for point $(1/5^{2l+2},(0.\vec v+1/5^l)/5^{2l+2})$.
Other segments are in more different inclinations,
or too short in the length.
Therefore $d(\;(1/5^{2l+2},(0.\vec v-1/5^l)/5^{2l+2}),f(I)\;)>1/5^{3l+3}$.

Thus, by Lemma \ref{nphard}, \(f(I)\) is in \( \NPhard_{\FF(\RR^2)} \).
	\qed


\section{ Conclusion }

We have shown three major results.
First is Theorem 1, which states that
the complexity of each self-similar set defined by a P-self-similar system
is nondeterministic polynominal time computable, that is,
the figure is in \( \NP_{\FF(\RR^2)} \).
The second is Theorem 2, which states that 
the complexity of each self-similar set defined by a P-self-similar system
with the P-open-set condition is polynominal time computable, that is,
 the figure is in \( \PP_{\FF(\RR^2)} \).
The third is Theorem 3, which provides 
an example of the image of a polynominal time computable H\"older function such that 
its Hausdorff dimension is 1 and
its computational complexity is NP-complete. 

Thus we conclude that the
classification by means of computable complexity does not coincide with 
the classification by means of the Hausdorff dimension.

\subsection*{Acknowledgement}

The authors would like to
thank Prof.~Yamaguchi Masaya, Prof.~Yasugi Mariko, and Prof.~Klaus Weihrauch for
their comments.

We especially express our gratitude to Prof.~Karen Brucks for her extensive help in preparing 
this paper. 

\bibliographystyle{plain}
%\bibliography.

\begin{thebibliography}{10}

\bibitem{Falconer'85}
K.~J. Falconer.
\newblock {\em The Geometry of Fractal Sets}.
\newblock Cambridge University Press, 1985.

\bibitem{Hata}
M.~Hata.
\newblock On the structure of self-similiar sets.
\newblock {\em Japan J.\ appl.\ Math.}, 2:381--414, 1985.

\bibitem{Hutchinson}
J.~E. Hutchinson.
\newblock Fractals and self-similarity.
\newblock {\em Indiana Univ.\ Math.\ J.}, 30(5):713--747, 1981.

\bibitem{Kawamura&Kamo'98}
Hiroyasu Kamo and Kiko Kawamura.
\newblock Computability of self-similar sets.
\newblock {\em Mathematical Logic Quarterly}, 45(1):23--30, 1999.

\bibitem{Kawamura&Kamo'97}
Kiko Kawamura and Hiroyasu Kamo.
\newblock Computability of self-affine sets.
\newblock {\em Annual Reports of Graduate School of Human Culture, Nara Women's
  University}, 12:135--150, 1997.

\bibitem{Ko}
Ker-I Ko.
\newblock On the computability of fractal dimensions and hausdorff measure.
\newblock {\em Annals of Pure and Applied Logic}, 93, 1998.

\bibitem{Morse}
D.~R. Morse, J.~H. Lawton, M.~M. Dodson, and M.~H. Williamson.
\newblock Fractal dimension of vegetation and the distribution of arthropod
  body lengths.
\newblock {\em Nature}, 314, 1985.

\bibitem{Pour-El&Richards}
M.~B. Pour-El and J.~I. Rechards.
\newblock {\em Computability in Analysis and Physics}.
\newblock Springer-Verlag, Berlin, Heidelberg, 1989.

\bibitem{Smith}
T.~G. Smith~Jr., W.~B. Marks, G.~D. Lange, W.~H. Sheriff~Jr., and E.~A. Neale.
\newblock A fractal analysis of cell images.
\newblock {\em J. Neurosci Met}, 27, 1989.

\bibitem{Weihrauch'87}
Klaus Weihrauch.
\newblock {\em Computability}.
\newblock Springer-Verlag, Berlin, Heidelberg, 1987.

\bibitem{Weihrauch'95}
Klaus Weihrauch.
\newblock A simple introduction to computable analysis.
\newblock Technical report, Fern Universit{\"a}t, Hagen, 1995.

\bibitem{Weihrauch'96}
Klaus Weihrauch.
\newblock A foundation of computable analysis.
\newblock {\em Proceedings of DMTCS '96}, 1996.

\end{thebibliography}

\end{document}

