Databases Reference
In-Depth Information
(u,v+2)
(0,u+v+2)
(0,u+v+2)
(u,v+1)
(0,u+v+1)
(0,u+v+1)
(u,v)
(0,u+v)
(0,u+v)
T(e,u,v)
(0,2)
(u,2)
(0,1)
(u,1)
(u,0)
(0,0)
Fig. 2.
Graphical representation of the privacy function f
PP
[Public] =
{
(u
,
v) : there is a path via f from (u
,
v) to (0
,
0)
}
It remains to be shown that We
≡
m
PP
[Public] where We is the eth
recursively enumerable set. Note that
≡
m is many-one equivalence.
COMP-We. (COMP-We is the complement of We)
The function h defined below is a many-one reduction function from
PP
[Public] to We.
Let a
∈
We and b
∈
h(u
,
v) = u if u
= 0 AND NOT
∃
w
vT(e
,
u
,
w)
= b if u
=0and
∃
w
vT(e
,
u
,
w)
= a if u = 0
The function k defined below is a many-one reduction function from We to
PP
[Public]. k(u) = (u, 0) for all u.
This proves Theorem 2(i).
Proof of Theorem 2(ii).
The privacy function f constructed for the proof of
Theorem 2(i) was a deterministic function. Therefore we have shown that
given a recursively enumerable set W, there is a situation S with determin-
istic privacy functions such that W is many-one equivalent to
PP
[Public]. It
has been shown that there exist recursively enumerable sets, which are not
creative. An example is the existence of a simple set [ROGE67]. Any set that
is many-one equivalent to a non-creative set is also non-creative. Therefore,
there is a situation in which
PP
[Public] is non-creative.
