Relativizing Small Complexity Classes and their Theories

Klaus Aehlig, Stephen Cook, Phuong Nguyen

Existing definitions of the relativizations of \NCOne, Ł and \NL\ do not preserve the inclusions $\NCOne \subseteq Ł$, $\NL\subseteq \ACOne$. We start by giving the first definitio…