On the Complexity of the Privacy Problem in Databases - Data Mining: Foundations and Practice - page 352

.
Since PP [L] is recursively enumerable and nonsimple, its complement has
a recursively enumerable subset. Let this subset be Q.
Given a triple

We now prove the result β

B, f, T , compute the following procedure:

Step 0: List B, f, T

Step r (r 0): Compute fr(B)

Note that f2(B) is f(f(B)) and f3(B is f(f(f(B)))

≥

(i) If fr(B) is empty, then list the members of PP [L] and stop the procedure
(note that the procedure does not terminate as PP [L] is infinite. What
we actually mean is do not go to step (r+1).
(ii) If fr(B) is assigned a privacy level by T which is not dominated by L
then enumerate the members of set Q and stop. (Note again that this
procedure does not halt).
(iii) If neither (i) nor (ii) hold, list fr(B), f, T ) and go to step (r + 1).

It can be shown that for each privacy level L, there is a recursive g such
that given an element

B, f, T the list enumerated is Wg( B, enumerated is

Wg( B, f, T ).

This proves Theorem 1(iii).
Proof of Theorem 1(iv). Let the privacy level L1 dominate the B, f, T belongs
to PP [L1] then B, f, T also belongs to to PP [L1] then B, f, T also belongs

to PP [L2].
If belongs to PP [L1] then there is an x which belongs to Cnf(B)

such that the privacy level of x is not dominated by L1. Then the privacy
level of x is also not dominated by L2. Therefore, x belongs to PP [L2]. That
is, PP [L1]

B, f, T

⊆ PP [L2].
(Note that we make the assumption that the same privacy function is used
for all privacy levels. Furthermore the constraints themselves are assumed to
be public. That is, the constraints are visible at all privacy levels.)

This proves Theorem 1(iv).
In Theorem 1 we have shown that the privacy problem is recursively enu-
merable with respect to all privacy levels. This does not mean that there is a
situation where the privacy problem is nonrecursive with respect to a privacy
level. By a situation we mean a particular scenario in the world. The privacy
functions and the privacy constraints used will be specific to a situation. As
the situation changes the privacy problem also changes. In Theorem 2 we
state some counter examples. A counter example depends on the particular
situation under consideration.
In Theorem 2 we assume that there are only two privacy levels: Private
and Public. This means at the private level there is no privacy problem. This
is because no constraint will assign a level that is higher than the private level
(e.g., highly private). Therefore the privacy problem at the private level will be