Verification of a maximal antichain

Question

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the antichain which is not properly contained in another antichain. Let's take the power set of $\{1,2,\ldots, n\}$ as our partially-ordered set, here the order is given by inclusion. Then my question is, for any given antichain of this partially-orded set, is there any polynomial-time algorithm (with respect to $n$) to verify that this antichain is indeed "maximal"? In other words, verifying that any subset of $\{1,2,\ldots, n\}$ is either contained in, or contains some set from the antichain. Here such algorithm should have polynomial run-time for ANY antichain.

Update: To clarify, here I will treat the size of our antichain as the parameter for the verification algorithm. In other words, my question is: does there exist a verification algorithm, whose run-time is polynomial in $n$ and $m$, where $m$ is the size of the antichain. When the size of our antichain $m$ is exponential in $n$ then such algorithm is trivial (just comparing those elements one by one); but when the given antichain has O(poly(n)) size, this is my interested case. For example, when the antichain is given by $\{\{1\}, \ldots, \{n\}\}$, we certainly do not have to do the brute force comparison.

Answer 1

Remark. Originally I claimed this to be a full solution, but that was false, as shown by Emil in the comments. However, this argument proves the following weaker version.

I can prove that it is co-NP-complete to decide for an input family $A$ whether there is a set $S$ that is unrelated to all sets in $A$. I'll call such families maximal. This shows that any possible polynomial time algorithm must exploit that the input family is an antichain, already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into a family $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
The complement of every pair is contained in $A$ regardless of $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i\notin S$ and false if $i'\notin S$, otherwise arbitrarily. This definition is indeed correct, as $\overline{ii'}\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.