E. Hemaspaandra et al., P-SELECTIVE SETS AND REDUCING SEARCH TO DECISION VS SELF-REDUCIBILITY, Journal of computer and system sciences, 53(2), 1996, pp. 194-209
Citations number
50
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
We distinguish self-reducibility of a language L with the question of
whether search reduces to decision for L. Results include: (i) If NE n
ot equal E, then there exists a set L in NP - P such that search reduc
es to decision for L, search does not nonadaptively reduce to decision
for L and L is not self-reducible. (ii) If UE not equal PE, then ther
e exists a language L is an element of UP - P such that search nonadap
tively reduces to decision for L, but L is not self-reducible. (iii) I
f UE boolean AND co-UE not equal E, then there is a disjunctive self-r
educible language L is an element of UP - P for which search does not
nonadaptively reduce to decision. We prove that if NE not subset of or
equal to BPE, then there is a language L is an element of NP--BPP suc
h that L is randomly self-reducible, not nonadaptively randomly self-r
educible, and not self-reducible. We obtain results concerning trade-o
ffs in multiprover interactive proof systems and results that distingu
ish checkable languages from those that are nonadaptively checkable. M
any of our results are proven by constructing p-selective sets, We obt
ain a p-selective set that is not less than or equal to (P)(tt)-equiva
lent to any tally language, and we show that if P = PP, then every p-s
elective set is less than or equal to (P)(T)-equivalent to a tally lan
guage. Similarly, if P = NP, then every cheatable set is less than or
equal to(T)(P)-equivalent to a tally language. We construct a recursiv
e p-selective tally set that is not cheatable. (C) 1996 Academic Press
, Inc.