Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170)

Strong nondeterministic machines are those types of Turing machines that define the class \(\text{NP}\cap\text{co-NP}\). When equipped with the additional feature of an ''advice'', as studied by Karp and Lipton, two different definitions are possible: a robust and non-robust version. Both versions are studied in this paper and compared. Related to this research, an oracle-restricted positive relativization of the probabilistic class ZPP is developed.