P-SELECTIVE SETS AND REDUCING SEARCH TO DECISION VS SELF-REDUCIBILITY

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.