Fix an -categorical structure . The simplest, and already interesting case is , the pure countable set.
We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) :
Input: Two definable graphs
Output: Yes, if and are isomorphic, No otherwise.
Below we make some very basic observations concerning this problem.