P-Selective Sets and Reducing Search to Decision vs Self-Reducibility

✍ Scribed by Edith Hemaspaandra; Ashish V. Naik; Mitsunori Ogihara; Alan L. Selman

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 684 KB
• Volume: 53
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0061

✦ Synopsis

We distinguish self-reducibility of a language L with the question of whether search reduces to decision for L. Results include: (i) If NE{E, then there exists a set L in NP&P such that search reduces to decision for L, search does not nonadaptively reduce to decision for L and L is not self-reducible. (ii) If UE{E, then there exists a language L # UP&P such that search nonadaptively reduces to decision for L, but L is not self-reducible. (iii) If UE & co-UE{E, then there is a disjunctive self-reducible language L # UP&P for which search does not nonadaptively reduce to decision. We prove that if NE 3 BPE, then there is a language L # NP&BPP such that L is randomly self-reducible, not nonadaptively randomly self-reducible, and not self-reducible. We obtain results concerning trade-offs in multiprover interactive proof systems and results that distinguish checkable languages from those that are nonadaptively checkable. Many of our results are proven by constructing p-selective sets. We obtain a p-selective set that is not P tt -equivalent to any tally language, and we show that if P=PP, then every p-selective set is P T -equivalent to a tally language. Similarly, if P=NP, then every cheatable set is P m -equivalent to a tally language. We construct a recursive p-selective tally set that is not cheatable.