数理解析研究所講究録
第 871 巻 1994 年 138-144

138

On Checkers, Self-Testers, and Self-Debuggers

東京工業大学総合理工学研究科 森啓悦 (Hiroyoshi Mori)
東京工業大学総合理工学研究科 伊東利哉 (Toshiya Itoh)1

Introduction

1.1

Background and Motivation

When a programmer writes a program that computes a function , one of the main difficulties
is correct. Blum and Kannan [BK] first attempted to
is to mathematically prove that
overcome this problem and introduced a notion of “program checking” as an application ofinteractive proofs [GMR], [BM]. Informally, a function is said to have a (program) checker
making calls to
outputs with high probability “correct” on
is correct,
if (1) when
outputs with highmaking calls to
any input $x\in\{0,1\}^{*}$ ; and (2) when ; is incorrect,
probability “incorrect” on any input $x\in\{0,1\}^{*}$ such that $P_{f}(x)\neq f(x)$ . Here we note that
only verifies the correctness of the output of any programonthe output of a checker
being
specified input $x\in\{0,1\}^{*}$ but does not guarantees the correctness of the program
checked. Then as an extension of checkers, Blum, Luby, and Rubinfeld [BLR] introduced anotion of self-tester/corrector, and self-tester/corrector pair,” which is a powerful tool in aif (1) whenpractical setting. Informally, a function is said to have a self-testerisoutputs “pass” with high probability; and (2) whentolerably faulty,
making calls to
outputs “fail” with high probability, and a function
is too faulty,
making calls tois not too faulty,
making calls to
is said to have a self-corrector
if when
outputs with high probability a correct answer for every input to . In addition, Blum, Luby,
and Rubinfeld [BLR] introduced a notion of self-tester/corrector pair,” which is a powerfultool in a practical setting.
Of course, we may expect that every function has a checker, a self-tester, and a self-corrector,
however, it is not the case. Indeed, there exists a function :that does not havea checker
under some complexity-theoretic assumption [Y], [BF], [BG]. As a relationshipamong checkers, self-testers, and self-correctors, Blum, Luby, and Rubinfeld [BLR] showed that
if a function has a checker , then has a self-tester(see Theorem 2.8). This implies
that the task of self-testers is not harder than that of checkers. On the contrary, it is not known
whether or not every function that has a checker has a self-corrector. Then$f$

$P_{f}$$P_{f}$$f$$C_{f}$$P_{f}$$C_{f}$$P_{f}$$P$$C_{f}$$P_{f}$$C_{f}$$P_{f}$$P_{f}$$f$$ST_{f}$$ST_{f}$$P_{f}$$ST_{f}$$P_{f}$$P_{f}$$P_{j}$$SC_{j}$$f$$SC_{f}$$P_{j}$$P_{f}$$f$$f$$\{0,1\}^{*}rightarrow\{0,1\}$$C_{f}$$f$.

$C_{f}$$f$

Question 1: Does every function$ST_{f}$$f$that has a checker have a self-corrector?

Intuitively, the task of self-correctors seems to be much harder than that of checkers. In section
3, we show that it is indeed the case assuming the existence of oneway permutations.
Blum, Luby, and Rubinfeld [BLR] also showed that if a function has a self-tester/corrector, then has a checker . It follows from the result above (see Theorem 2.8)
pair {
that if a function has a self-tester/corrector pair (. It}, then has a self-tester
should be noted that the resulting self-tester
for could be very reliable but it is somewhat
inflexible for a practical purpose, i.e.,
only passes completely correct programsforbut does not pass almost correct programsfor . Then
$f$

$f$

$\overline{ST}_{f},\overline{SC}_{f}\rangle$$C_{f}$$f$$\overline{ST}_{f},\overline{SC}_{f}$$f$$ST_{f}$$f$$ST_{j}$$ST_{f}$$P_{f}$$P_{f}$

$f$

$f$

139

.

Question 2: How can we make self-testers for a function$f$reliable and flexible?

To investigate this problem, we introduce in section 4 a novel notion of “self-debuggers” forand then present in subsection 5.1 a way to design a reliable and flexible self-tester for fromany self-tester/corrector pair for .
$f$

$f$

$f$

Results

1.2

In this paper, we first present a negative solution to Question 1, i.e., if oneway permutations
exist, then there exists a function : $\{0,1\}^{*}rightarrow\{0,1\}$ that has a checker but does not have aself-corrector (see Theorem 3.1). To demonstrate a positive solution to Question 2, we introduce
in section 4 a novel notion of “self-debuggers” and then show that if a function has a selftester/corrector pair ((see Theorem 4.2). As the}, then has a self-debugger, ifapplications of self-debuggers, we show in subsection 5.1 that for any
is an-self-tester for andsuchis an -self-corrector for , then for any, there exists an-self-testerfor (see Theorem 5.1) and in subsection
that
, if
is an
-self-tester for andis an
5.2 that for any-self-corrector for , then for any constant $\delta>0$ such that, there exists an-selffor (see Theorem 5.2). The result of Theorem 3.1 captures our intuition thatdebuggerthe task of self-correctors seems to be much harder than that of checkers and the results ofTheorems 5.1 and 5.2 provides us a powerful tool in a practical setting.
$f$

$f$

$\overline{ST}_{j},\overline{SC}_{f}$$f$$SD_{f}$$0<\epsilon_{1}’<\epsilon_{2}’\leq\epsilon’<1$$f$$(\epsilon_{1}’, \epsilon_{2}’)$$\overline{ST}_{f}$$\epsilon_{1}\leq\epsilon’$$ST_{f}$$(\epsilon_{1}, \epsilon_{2})$$0<\epsilon_{1}’<\epsilon_{2}’\leq\epsilon’<1$$f$$\epsilon’$$\overline{SC}_{f}$$\overline{ST}_{j}$$f$$(\epsilon_{1}’, \epsilon_{2}’)$$f$$\epsilon’$$\epsilon_{1}<\epsilon_{2}$$f$$\overline{SC}_{j}$$\delta\leq\epsilon’$$(\epsilon’, \delta)$$f$$SD_{f}$Preliminaries

2

In this section, we first present definitions and terminologies necessary to the subsequent technical discussions and then overview the results known so far.

Definitions and Terminologies

2.1

be a function and let
Let :be a program that purports to compute . In
this paper, any programis assumed to be static, i.e.,
is completely determined by the$x\in\{0,1\}^{*}$
input
and does not depend on any input previously asked of the program
current
to denote the output of a program. We use
on input $x\in\{0,1\}^{*}$ . A program$x\in\{0,1\}^{*}$
for is said to be correct if $P_{J}(x)=f(x)$ for every
and a programfor is said
to be incorrect if there exists $w\in\{0,1\}^{*}$ such that $P_{j}(w)\neq f(w)$ .
$f$$\{0,1\}^{*}-\rangle$$\{0,1\}^{*}$$P_{j}(x)$$P_{j}(x)$$P_{f}$$f$$P_{f}$$P_{f}$$P_{j}$$P_{j}$$f$$f$$P_{f}$(proba bilistic) rogram $M$ is said to be an oracle program if it
Definition 2.1 [BLR]:
is allo wed to make $calls$ to anoth er program that is specified at its run time. $We$ use
todenote an oracle program $M$ that makes alls to an other rogram .
$A$

$p$

$M^{A}$

$c$

$A$

$p$

Definition 2.2 [BK]: A proba bilistic polynomial time oracle programis aid to be a$\{0,1\}^{*}\mapsto\{0,1\}^{*}if$
every
for
programthat purports to compute
checker for a function :$f,$on in $putx\in\{0,1\}^{*}$ satisfies the following con dition :$C_{f}$$f$$C_{f}$(1) If$s$$P_{j}$$s$$P_{f}$

is correct, then $Pr$ {$C_{f}^{P_{f}}(x)=$”correct”}$\geq 2/3$

for $anyx\in\{0,1\}^{*}$ ;(2) For any $x\in\{0,1\}^{*}such$ that $P_{f}(x)\neq f(x),$ $Pr\{C_{f}^{P_{f}}(x)=c_{1ncorrect’\}}\geq 2/3$ ,where the robabilities are aken over all possibk coin tosses of
$p$

$t$

$C_{j}$.

140
on any input $x\in\{0,1\}^{*}$ such that $P_{f}(x)=f(x)$Note that in Definition 2.2, the output ofincorrect.
iswhen
specified
is notfor
We say that a function is checkable (or has a checker) if there exists a checker
$eL$
for
its
is checkable (or has a checker) if there exists a checker
and also that a languag
characteristic function . A function (or a language ) is uncheckable if it is not checkable.
. Let
be a sequence of
Let $N$ be a set of positive integers and let
subsets of that satisfies $I_{1}\cup I_{2}\cup\cdots=I$ . Note that each $n\in N$ indicates the “size” of each
. We use $D=\{D_{n}|n\in N\}$ to denote an ensemble of probability distributions such thatbe a program that purports to compute afor each $n\in N$ . Let
is a distribution on
function . We use Err $(P_{f}, f, D_{n})$ to denote the error probability that $P_{f}(x)\neq f(x)$ when isfor $n\in N$ . Let $0<\beta<1/2$ be a confidence parameter.
according torandomly chosen in$C_{f}^{P_{f}}$$P_{f}$$f$$f$$C_{L}$$L$$f$$\lambda_{L}$$f$$C_{f}$$L$$I\subseteq\{0,1\}^{*}$$I_{1},$$\cdots\subseteq I$$I_{2},$$I$$x\in I_{n}$$D_{n}$$I_{n}$$P_{j}$$f$$x$$D_{n}$$I_{n}$

is said to be
Definition 2.3 [BLR]: A probabilistic polynomial time oracle program-self-tester for fun ction with respect to $\mathcal{D}=\{D_{n}|n\in N\}$ if for some constantsanon input 1 $n0<\beta<1/2$
that purports to $com$ pute $f,$
and any programsatisfies the following conditions:$ST_{f}$$(\epsilon_{1}, \epsilon_{2})$

$f$

$a$

$0\leq\epsilon_{1}<\epsilon_{2}\leq 1$$ST_{f}$$P_{f}$(1) If Err$(P_{f}, f, D_{n})\leq\epsilon_{1}$, then $Pr$ {$ST_{f}^{P_{f}}(\langle 1^{n},$$\beta\rangle)=$“pass”}(2) If Err$(P_{f}, f, D_{n})\geq\epsilon_{2}$, then $Pr$ {$ST_{f}^{P_{f}}(\langle 1^{n},$$\beta\rangle)=$“fail”}$\geq 1-\beta$$\geq 1-\beta$

where the pro babilities are aken over all possi ble oi tosses of
$t$

$n$

$c$

$ST_{f}$;,.

is not specified when.
Note that in Definition 2.3, the output ofshould be as close as possible to so that
Thus the value
is reliable.
We say that a function is weakly/strongly self-testable (or has a $weak/strong$ self-tester)
if for some/any ensemble of distributions , there exist some constantssuch-self-testerwith respect tothat has an
and we also say that a language
is weakly/strongly self-testable (or has a weak/strong self-tester) if for some/any ensembleof distributions , there exists some constants
such that its characteristicwith respect to . A function (or a language ) isfunction-self-tester
has ansaid to be strongly/weakly self-untestable if it is not weakly/strongly self-testable.
$\epsilon_{1}<Err(P_{f}, f, D_{n})<\epsilon_{2}$$ST_{f}$$0$$\delta=\epsilon_{2}-\epsilon_{J}$$ST_{f}$

$f$

$f$

$D$

$f$

$0\leq\epsilon_{1}<\epsilon_{2}\leq 1$$ST_{f}$$(\epsilon_{1}, \epsilon_{2})$$L$$\mathcal{D}$$L$$0\leq\epsilon_{1}<\epsilon_{2}\leq 1$$\mathcal{D}$$\lambda_{L}$$D$$ST_{L}$$(\epsilon_{1},\epsilon_{2})$

$L$

$f$

Definition 2.4 [BLR]: A pro babilistic polynomi time $oracle$ programis said to be $an$
-self-corrector for a functi on with respect to $D=\{D_{n}|n\in N\}$ if for $somecon$ stant $0<\epsilon<1$that purports to compute $f,$$0<\beta<1/2$ satisfies
and any program
on input, thenthe following condition: If Err.
$al$$SC_{f}$$f$$\epsilon$$SC_{f}$$P_{j}$$1^{n},$$x\in I_{n},$$Pr\{SC_{f}^{P_{j}}(\langle 1^{n}, x, \beta\rangle)=f(x)\}\geq 1-\beta$$(P_{f}, f, D_{n})\leq\epsilon$

We also say that a function is weakly/strongly correctable (or has a $weak/strong$ selftester), that a language is weakly/storngly correctable (or has a weak/storng self-tester),and that a function (resp. a language ) is strongly/weakly self-uncorrectable in a way similar
to the case of self-testers.
$f$

$f$

$L$

$L$

$L$

$f$

Definition 2.5 [BLR]: A pair of proba bilistic polynonial time oracle programs
is aid to $be$ a self-tester/corrector pair for fun ction if for some constants
and an en semble of distribu tions $D,$is an-self-tester for $fwi$ th respect tois an e-self-corrector for with respect to .

$\langle ST_{f}, SC_{f}\rangle$

$f$

$a$

$s$

$ST_{f}$$(\epsilon_{1}, \epsilon_{2})$

$D$

and

$D$

$f$

$SC_{f}$$0\leq\epsilon_{1}<\epsilon_{2}\leq\epsilon<1$

We say that a function (resp. a language ) has a self-tester/corrector pair if there exists
a self-tester/corrector pair for (resp. the characteristic functionof ).
For each $n\geq 0$ , let $S_{n}=\{0,1\}^{n}$ and let
be a set of all possible sequences of coin toss esof a probabilistic polynomial (in n) time algorithm on input of length .
$L$

$f$

$f$

$L$

$\lambda_{L}$$R_{n}$$n$141
Definition 2.6 (Oneway Permutation):

If a function $g:\{0,1\}^{*}\mapsto\{0,1\}^{*}$ satisfies that

(1) For any $x\in\{0,1\}^{*},$ $|g(x)|=|x|$ and is 1-1 and onto;(2) For any $x\in\{0,1\}^{*},$ $g(x)$ can be evaluated in polyn omial (in ) time;(3) For any pro ba bilis $tic$ polynomial (in n) time algorithm and each $con$ stant $c>0$ , there
exi $sts$ a $con$ stan $tN_{c}\geq 0$ such that $Pr\{g(A(y))=y\}<n^{-c}$ for every $n>N_{c}$ and every$y\in\{0,1\}^{n}$ , where the probabili ties are taken over
,
}
$g$

$|x|$

$A$

$\langle y,r$then we say that the fun $cti$ on$g:\{0,1\}^{*}arrow\rangle$$\in S_{n}\cross R_{n}$is a oneway permutation.

$\{0,1\}^{*}$

for each $n\in N$ to denote the:In the rest of this paper, we sometimes use.
restriction of a oneway permutation :The following inequality is useful in section 5.1 to approximate the error probability (withthat purports to compute .
respect to ) of a program$\{0,1\}^{n}\mapsto\{0,1\}^{n}$$g_{n}$$g$$D$$\{0,1\}^{*}$$\{0,1\}^{*}arrow\rangle$$f$$P_{f}$

be in dependent identically distributed 0-1 random
Definition 2.7 [S]: Letvaria bles and let $Pr(X;=1)=p$ for each $i(1\leq i\leq n)$ . Then
$X_{1},$ $X_{2},$$\ldots,$$X_{n}$;(1)$Pr\{\frac{1}{n}\sum_{=:1}^{n}X_{i}-p\leq\delta\}\geq 1-\exp\{-\frac{\delta^{2}n}{2}\}$(2)$Pr\{\frac{1}{n}\sum_{\mathfrak{i}=1}^{n}X;-p\geq-\delta\}\geq 1-\exp\{-\frac{\delta^{2}n}{2}\}$for any integer $n\geq 1$ and any constant$\delta>0$,.

Known Results

2.2

Here we overview the known results on checkers, self-testers, and self-correctors. The following
theorems are the relationships among checkers, self-testers, and self-correctors.

Theorem 2.8 [BLR], [R]: If a function : $\{0,1\}^{*}rightarrow\{0,1\}^{*}has$ a checker , then for any, the function has a-self-testerwith respect to any polynomialconst antime samplable ensemble of distribution $sD$ .
$f$$t0<\epsilon_{2}\leq 1$$C_{f}$$(0, e_{2})$$f$$ST_{f}$

Theorem 2.9 [BLR]: If a fun ction : $\{0,1\}^{*}rightarrow\{0,1\}^{*}h$ as a self-tester/corrector pair), then the function has a checker .
\langle$f$$f$$ST_{f},$ $SC_{f}$3$C_{f}$

Checkable But Self-Uncorrectable Languages

In this section, we give a solution to Question 1 in subsection 1.1, i.e., there exists a weakly
self-uncorrectable language that is checkable under a complexity-theoretic assumption.
$L$

Theorem 3.1:
language

If oneway permutation exist, then there exists a weakly self-uncorrectablethat $Aas$ checker.
$s$$L\not\in \mathcal{B}PP$$a$

Proof: Let $I=\{\{0,1\}^{n}\cross\{0,1\}^{n}\cross\{0,1\}^{n}|n\in N\}$ and let $I_{n}=\{0,1\}^{n}\cross\{0,1\}^{n}\cross\{0,1\}^{n}$for each $n\in N$ . We use $\mathcal{U}=\{U_{n}|n\in N\}$ to denote an ensemble of uniform distributions, i.e.,
to denote the inner product ofis a uniform distribution on , and use
for each $n\in N,$$b\in\{0,1\}^{n}$ modulo 2. Let:
be a oneway permutation. Define a language
to be $L_{g}=\{\langle y,p,0^{|y|})\in I|g^{-1}(y)\cdot p=1\}$ . It is obvious that
. Note that theis inspired by the hard-core predicate due to Goldreich and Levin [GL].
definition of$U_{n}$$a,$$I_{n}$$g$$a\cdot b$$\{0,1\}^{*}rightarrow\{0,1\}^{*}$$L_{g}\in \mathcal{N}P$$L_{g}\subseteq I$$L_{g}$

142
has a checker . But there isn’t enough space to show that. So we
We first show that
proof.
theobmit
is weakly self-uncorrectable. Indeed, we show that for some ensemble
Next, we show that$\mathcal{D}=\{D_{n}|.n\in
N\}$ and for any constant $0<\epsilon<1$ , the characteristic functionof distributions
does not have an -self-corrector with respect to $\mathcal{D}=\{D_{n}|n\in N\}$ .
ofis strongly self-correctable, i.e., for any ensemble of distributions and someAssume thathas an e-self-corrector with respect to . Then this means that for
constant $0<\epsilon<1,$
has an e-self-corrector
with respect to $\mathcal{U}=\{U_{n}|n\in N\}$ ,some constant $0<\epsilon<1,$$n\inN$
for each. Define a program that purports
is a uniform distribution on
where,
in a way that on input
to cumpute$C_{g}$$L_{g}$$L_{g}$$L_{g}$$\lambda_{g}$$\epsilon$$\mathcal{D}$$L_{g}$$D$$L_{g}$$L_{g}$$SC_{g}^{e}$$\tilde{P}_{g}$$I_{n}$$U_{n}$$\langle y,p, z\rangle\in I_{n}$$\lambda_{g}$$\tilde{P}_{g}(\langle y,p, z\rangle)=\{01$errs only for ( $y,p,$Here we note that(oneway) permutation, it follows that for each $n\in N,$$0^{n}\rangle$$\tilde{P}_{9}$Err.

$z\neq 0_{n};z=0^{n}$$\not\in L_{g}\cap I_{n}$. From the assumption that$Err(\tilde{P}_{g}, \lambda_{g}, U_{n})$$g_{n}$

is a

is given by,$( \tilde{P}_{g}, \lambda_{g}, U_{n})=\frac{\Vert\{\langle y,p,0^{n}\}\in I_{n}|g^{-1}(y)\cdot p=0\}\Vert}{\Vert I_{n}||}=\frac{2^{2n-1}+2^{n-1}}{2^{3n}}=\frac{2^{n}+1}{2^{2n+1}}<\frac{1}{2^{n}}$denotes the cardinality of a finite set .
where. This implies that for every,
Then for every
outputs 1 with probability at least $1-\beta$ if
making calls to the programand outputs with probability at least $1-\beta$ if. Thus we can make probabilisticwith probability at
polynomial (in n) time program
such thatleast $1-\beta$ fromand . Since $0<\beta<1/2$ is a constant (see Definition 2.4),[BDG]. By a standard technique (see [BDG]), we assume without loss of generality that there
exists a probabilistic polynomial (in n) time algorithm such thatwith probability at least $1-2^{-n}$ . Then let us consider the following probabilistic algorithm$A$$\Vert A\Vert$$n\geq\lceil\log\epsilon^{-1}\rceil,$$Err(\tilde{P}_{g}, \lambda_{g}, U_{n})\leq\epsilon$$n\geq\lceil\log e^{-1}\rceil$$\langle y,p, z\rangle\in L_{g}$$\tilde{P}_{g}$$SC_{g^{\zeta}}$$0$$\langle y,p, z\rangle\not\in L_{9}$$\hat{P}_{g}(\langle y,p, z\rangle)=\lambda_{g}(\langle y,p, z\rangle)$$\hat{P}_{g}$$\tilde{P}_{g}$$C_{g}$$L_{g}\in \mathcal{B}\mathcal{P}P$$G$$Inv_{g}$$G(\{y,p, z\rangle)=\lambda_{9}(\{y,p, z\rangle)$:

Inverting Algorithm$Inv_{g}$:Input: $y\in\{0,1\}^{n}$ .
(null string); $j:=1$ .
I-O:
I-l: Choose randomly $p\in\{0,1\}^{n}$ .
to get $b=G((y,p, 0^{n}\rangle)$ .
I-2: Run on input
to get.
I-3: Run on input
I-4: If $b=b_{j}$ , then $x:=x\Vert 0$ and $j:=j+1$ ; otherwise $x:=x\Vert 1$ and $j:=j+1$ .
I-5: If $j\leq n$ , then go to step I-3; otherwise continue.
I-6: If $y=g(x)$ , then halt and output $x\in\{0,1\}^{n}$ ; otherwise halt and output$x:=\epsilon$$G$$\langle y,p, 0^{n}\rangle$$G$$\langle y,p\oplus e_{i}^{n}, 0^{n}\rangle$$b_{j}=G(\langle y,p\oplus e_{j}^{n}, 0^{n}\rangle)$$”\perp$.

It is obvious that if correctly returns and for each $j(1\leq j\leq n)$ , thensuccessfully
finds in polynomial time $x\in\{0,1\}^{n}$ such that $y=g(x)$ (see [GL]). Thus the probability
outputs $x\in\{0,1\}^{n}$ such that $y=g(x)$ is bounded bythat on input $y\in\{0,1\}^{n},$
$G$

$b$

$Inv_{g}$$b_{j}$$P_{succ}$$Inv_{g}$$P_{succ}\geq(1-2^{-n})^{n+1}\geq 1-(n+1)\cdot 2^{-n}$.

This contradicts the assumption that is a oneway permutation (see Definition 2.6). Then it
follows thatand this implies thatmust be weakly self-uncorrectable.
Thus if oneway permutations exist, then there exists a weakly self-uncorrectable languagethat has a different checker.
$g$$L_{g}\not\in \mathcal{B}\mathcal{P}\mathcal{P}$$L\not\in \mathcal{B}\mathcal{P}P$$L_{g}$$\blacksquare$143
Self-Debuggers

4

In this section, we present a new notion of “self-debuggers.” Informally, a function is said towith respect to $D$ iftransforms a faulty program
for $f$ withhave a self-debugger
for with respect to $D$ .
respect to $D$ to a less faulty (deterministic) program$f$$SD_{f}$$SD_{f}$$P_{f}$$f$$Q_{f}$

is said to be a
A probabilistic polynomial time oracle program$D=\{D_{n}|n\inN\}$
if for some $con$ stants
self-debugger for a function with respect to$0<\beta<1/2$ transforms any programthat purports to computeon inputfor and it satisfies the following $con$ ditions:to a (deterministic) program

Definition 4.1:

$SD_{f}$$(\delta,\gamma)-$$f$$\delta\leq 1,$$SD_{j}$$0\leq\gamma\leq$$1^{n},$$P_{f}$(1) If Err$(P_{j}, f, D_{n})\leq\delta$

$f$

$f$

$Q_{f}^{n}$, then $Pr\{Err(Q_{f}^{n}, f, D_{n})\leq\gamma\}\geq 1-\beta$ ;(2) If Err $(P_{j}, f, D_{n})>\delta$ , then$Pr\{SD_{f}^{P_{f}}(\langle 1^{n}, \beta\})=‘$

fail“VErr

where the probab ilities are taken over all possible oin tosses of$c$

The following theorem shows that if a function
exists a self-debugger for .

$f$$(Q_{f}^{n}, f,D_{n})\leq\gamma$}$\geq 1-\beta$,$SD_{f}$has a self-tester/corrector pair, then there$f$Theorem 4.2: For some const an $ts0<\epsilon_{1}’<\epsilon_{2}’\leq e’<1$ and a polynomial time amplable
ensemble of distributions , let {is a self-tester/corrector pair for fun ction $f,$ $i.e.$ ,is an
is an -self-corrector for with-self-tester for with respect to $D$ an
$ect$
resp
to D. Then there exists an-debugger
for with resp $ect$ to $D$ .
$s$$\overline{ST}_{f},\overline{SC}_{f}\rangle$$\mathcal{D}$$\overline{ST}_{f}$

$a$

$f$

$(\epsilon_{1}’,\epsilon_{2}’)$$d\overline{SC}_{f}$5$f$$\epsilon’$$f$$SD_{f}$$(\epsilon’,\epsilon_{2}’)- se|f$Applications of Self-Debuggers

In this section, we present two applications of self-debuggers by using Theorem 4.2. The first
application is to design a reliable and flexible self-tester from any self-tester/corrector pair andthe second application is to design strong self-debugger from any self-tester/corrector pair.

5.1

Making Self-Testers Reliable and Flexible

isAssume that a self-tester/corrector pair \langle} for a function :given. Then it follows from Theorem 2.9 that has a checker
and it follows from Theorem-self-testerwith respect to any
2.8 that for any constant $0<\epsilon_{2}\leq 1,$ has a
can bepolynomial time samplable ensemble of distributions . The resulting self-tester
is taken to be very small. On the other hand,is somewhat ofhighly reliable whenfor . We often wish tolimited use, because it only passes completely correct programs
passes almost correct programsfor in such a way thatdesign a flexible self-tester
for . In this section, we give (as a solution to Question 2) a way to design a reliable andflexible self-tester for from any self-tester/corrector pair for .
$f$$\overline{ST}_{f},\overline{SC}_{f}$

$f$

$f$

$\{0,1\}^{*}rightarrow\{0,1\}^{*}$$C_{f}$$(0,\epsilon_{2})$$ST_{f^{2}}^{e}$$\mathcal{D}$$ST_{f^{2}}^{e}$$ST_{j^{\epsilon_{2}}}$$\epsilon_{2}$$P_{f}$$f$$ST_{j}$$\tilde{P}_{f}$$f$$ST_{f}$

$f$

$f$

$f$

an a olynomial time sampla $ble$
Theorem 5.1: For some constants
is a $self- teste\acute{r}/corrector$ pair for a function , i.e.,
ensemble of $dis$ tribution $sD$ , let
is an $e’- self$-corrector for withis an-self-tester for with respect to and, there exists ansuch that-self-tester
respect to . Then for any onst ants
for with respect to .
$0<\epsilon_{1}’<\epsilon_{2}’\leq e’<1$

$d$

$p$

$f$

$\langle\overline{ST}_{f},\overline{ST}_{j}\rangle$$\overline{ST}_{f}$$\mathcal{D}$$ST_{f}$

$f$

$D$

$f$

$(\epsilon_{1}’,\epsilon_{2}’)$

$c$

$D$

$e_{1}<\epsilon_{2}$$f$$\overline{SC}_{f}$$\epsilon_{1}\leq\epsilon’$$(\epsilon_{1}, \epsilon_{2})$144
Amplffication of Self-Debuggers

5.2

From Theorems 4.2 and 5.1, we can show the following theorem:
Theorem 5.2:
For some $con$ stants $0<\epsilon_{1}’<e_{2}’\leq\epsilon’<1$ and a polyn om $ial$ time samplable ensemble ofbe $con$ stants and let
be a polynomial time
distributions $D$ , let Let
self-tester/corrector
pair for a $fun$ ction ,
ions.
is
a
samplable ensemble of distribut$i.e.,$
is an -self-corrector for with-self-tester for with respect to an
is an, there exists an-self-debugger
resp $ect$ to . Then for any constan $t\delta>0$ such thatfor with respect to .
$0<\epsilon_{1}’<\epsilon_{2}’\leq n\epsilon’<1$$\mathcal{D}$$f$$\{\overline{ST}_{f},\overline{ST}_{j}\}$$f$$(\epsilon_{1}’, e_{2}’)$$\overline{ST}_{f}$$d\overline{SC}_{f}$

$f$

$f$

$\epsilon’$$\delta\leq\epsilon’$$\mathcal{D}$$SD_{f}$$D$$(e’, \delta)$$\mathcal{D}$Proof: This can be led from Theorem 5.1 and Theorem 4.2 easily.

Acknowledgments
The authors wish to thank Ronitt Rubinfeld for her helpful discussion on the relation between
checkers and self-testers [R].

References[BDG] Balc\’azar, J.L., D\’iaz, J., and Gabarr6, J., “Structural Complexity I,” EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin (1988).

[BF] Beigel, R. and Feigenbaum, J., “On Being Coherent Without Being Very Hard,” Computational Complexity, Vol.2, No.1, pp.1-17 (1992).
[BG] Bellare, M. and Goldwasser, S., “The Complexity of Decision versus Search,” to appear

in SIAM Journal on Computing.

[BK] Blum, M. and Kannan, S., “Designing Programs That Check Their Work,” Proceedings
of $STOC’ 89$ , pp.86-97 (1989).
[BLR] Blum, M., Luby, M., and Rubinfeld, R., Self-Testing/Correcting with Applications
to Numerical Problems,” Journal of Computer and Systems Sciences, Vol.47, No.3,
pp.549-595 (1993).

[BM] Babai, L. and Moran, S., “Arthur-Merlin Games: A Randomized Proof Systems and a
Hierarchy of Complexity Classes,” Journal of Computer and System Sciences, Vol.36,
pp.254-276 (1988).
[GL] Goldreich, $0$ . and Levin, L.A., “A Hard-Core Predicate for All One-Way Functions,”
Proceedings of $STOC’ 89$ , pp.25-32 (1989).
[GMR] Goldwasser, S., Micali, S., and Rackoff, C., “The Knowledge Complexity of Interactive
Proof Systems,” SIAM Journal on Computing, Vol.18, No.1, pp.186-208 (1989).

[R] Rubinfeld, R., private communication (1993).
[S] Spencer, J., “Ten lectures on the Probabilistic Method,” CBMS-NSF Regional Conference Series in Applied Mathematics 52, SIAM (1987).
[Y] Yao, A., “Coherent Functions and Program Checkers,” Proceedings of $STOC’ 90$ , pp.84$94_{1\backslash }(1990)$.