On helping by robust oracle machines (Q1097695): Difference between revisions

The concept of helping using robust oracle Turing machines (TM) was first introduced by \textit{U. Schöning} [Theor. Comput. Sci. 40, 57--66 (1985; Zbl 0574.68041)]. An oracle TM is robust if its output on an input \(x\) does not change when oracle changes its answers to the queries made by the TM. Thus, an oracle can only affect the computation time used by the machine. An oracle is said to help a robust TM if the machine runs in polynomial time using this oracle. Certain interesting structural properties about helping sets in NP have been observed by Schöning. Some more are observed in this paper. For example, the class \(\mathrm{UP}\cap \mathrm{co-UP}\) helps exactly sets in the same class, where UP is the class of sets computable by unambiguous NP machines [\textit{L. G. Valiant}, Inf. Process. Lett. 5, 20--23 (1976; Zbl 0342.68028)]. New notions of helping such as one-sided helping, self-helping are studied and compared with other standard notions of complexity theory such as self-reducibility and sparseness. Several known properties of these standard complexity notions are reproved from the viewpoint of helping.