Robust machines accept easy sets
Juns Hartmanis, Lane A. Hemaspaandra · Theoretical Computer Science · 1990
A robust machine is a machine that maintains some computational property for every oracle. In this paper we study robustly complementary, robustly categorical, robustly ∑∗-accepting, and robustly ∑∗-spanning machines. We prove that robust machines squander their powerful nondeterministic oracle access in all relativizations—relative to any oracle A, their languages and properties can be computed in PNPA.