CHECKERS FOR ADAPTIVE PROGRAMS

Let L congruent-to {0, 1} be a language and let lambda(L): {0, 1}* ba r arrow pointing right {0, 1} be the characteristic function of the la nguage L, i.e., if x is-an-element-of L, lambda(L) (x) = 1; otherwise, lambda(L) (x) = 0. In this paper, we consider an adaptive checker wit h a single program F (resp. noncommunicating multiple programs F1, F2, ...) for lambda(L) that works even when an incorrect program F (resp . incorrect noncommunicating multiple programs F1, F2*, ...) for lamb da(L) adaptively behaves according to inputs previously provided to th e program F (resp. the programs F1*, F2*, ...). We show that (1) for any language L, there exists an adaptive checker with a single program for lambda(L) iff L and LBAR respectively have competitive interactiv e proof systems; and (2) that for any language L, there exists an adap tive checker with noncommunicating multiple program for lambda(L) iff L and LBAR respectively have function-restricted interactive proof sys tems. This implies that for any language L, adaptive checkers with non communicating multiple programs for lambda(L) are as powerful as stati c ones with a single program for lambda(L).