On the Computational Complexity of Defining Sets

Hamed Hatami, Hossein Maserrat

Suppose we have a family $\mathcal{F}$ of sets. For every $S\in \mathcal{F}$, a set $D\subseteq S$ is a {\sf defining set} for $(\mathcal{F},S)$ if $S$ is the only element of $\mathcal{F}$ th…