We look at the non-uniform complexity classes $\bP/poly$ and its variations $\bL/poly$, $\bNL/poly$, $\bNP/poly$ and $\bPSpace /poly$, and look for analogues of the Ajtai-Immerman theorem which characterizes $\bAC_0$ as the non-uniformly First Order Definable classes of finite structures. We have previously observed that the Ajtai-Immerman theorem can be rephrased in terms of {\em invariant definability}: A class of finite structures is $FOL$ invariantly definable iff it is in $\bAC_0$.
Invariant definability is a notion closely related to but different from {\em implicit definability} and {\em $\Delta$-definability}. Its exact relationship to these other notions of definability has been determined in {\em J.A. Makowsky, Invariant Definability, in Computational Logic and Proof Theory, Proceedings of the 5th Kurt G\"odel Colloquium, KGC'97, Vienna, August 1997, LNCS vol. 1289 (1997), pp. 186-202. }
Our main result here can be stated as follows: Let $\bC$ be one of $\bL, \bNL, \bP$, $\bNP$, $\bPSpace$ and $\cL$ be a logic which captures $\bC$ on ordered structures. Then the $\cL$-invariantly definable classes of (not necessarily ordered) finite structures are exactly the classes in $\bC/poly$. We also consider uniformity conditions on the advice sequences and obtain analogous results.