Strong and robustly strong polynomial-time reducibilities to sparse sets

AbstractReducibility defined by oracle strong nondeterministic machines is studied. Two definitions of relativized strength are presented and separated. The corresponding reduction classes of the sparse sets give two nonuniform analogs of the class NP∩coNP. An oracle-restricted positive relativization of the probabilistic class ZPP is developed