On Helping by Robust Oracle Machines
Ker‐I Ko · 1987
The concept of helping by robust oracle Turing machines, introduced recently by Schöning, is extended to the notion of "one-sided helping" and its relations to the structural properties of Ν Ρ sets are investigated. Various results on who can help whom have been obtained on sets in BPP, in R, in UP and sparse sets. Sets which do not help any set are studied and two types of sets defined by structural properties are demonstrated to help no sets except those in P. Sets which help themselves are also studied and are shown to be related to self-reducible sets. Several previously known structural results on ΝΡ sets are reproved from the point of view of helping.