  Suppose we have a family ${\cal F}$ of sets. For every $S \in {\cal F}$, a
set $D \subseteq S$ is a {\sf defining set} for $({\cal F},S)$ if $S$ is the
only element of $\cal{F}$ that contains $D$ as a subset. This concept has been
studied in numerous cases, such as vertex colorings, perfect matchings,
dominating sets, block designs, geodetics, orientations, and Latin squares.
  In this paper, first, we propose the concept of a defining set of a logical
formula, and we prove that the computational complexity of such a problem is
$\Sigma_2$-complete.
  We also show that the computational complexity of the following problem about
the defining set of vertex colorings of graphs is $\Sigma_2$-complete:
  {\sc Instance:} A graph $G$ with a vertex coloring $c$ and an integer $k$.
  {\sc Question:} If ${\cal C}(G)$ be the set of all $\chi(G)$-colorings of
$G$, then does $({\cal C}(G),c)$ have a defining set of size at most $k$?
  Moreover, we study the computational complexity of some other variants of
this problem.
