Finding longest chain in poset in subquadratic time
Well, start by observing that

when A has no comparable pairs, the height will be 0
and
when A has one or two comparable pairs, the height will be 1

.
Thus, when ​ $\leq$ ​ is given with one bit for each ordered-pair of distinct elements,

even promised-to-be-at-most-1 height will have

co-nondeterministic query complexity ​ $(|\hspace{.02 in}A|\hspace{-0.03 in}\cdot \hspace{-0.03 in}(|\hspace{.02 in}A|\hspace{-0.04 in}-\hspace{-0.05 in}1))\hspace{.02 in}/\hspace{.02 in}2$

and probabilistic query complexity ​ $\Theta$$\left(\hspace{-0.02 in}|\hspace{.02 in}A|^2\right)$ .

Accordingly, we can only hope for better when ​ $\leq$ ​ is given in some other way,

like as a list of the pairs for which it's true or as

an $A$-indexed array of ordered-pairs of lists, such that for each element $a$ of $A$,

$a$'s left list is the $a'$ such that ​ $a' &lt; a$ ​ and $a$'s right list is the $a'$ such that ​ $a &lt; a'$

.
(I currently have no clue regarding the complexity for such representations of ​ $\leq$ .)



For your case of interest:

See this question and its answer.

(That answer's universe size is your n and that answer's n is your ​ $|\hspace{.04 in}A|$ .)

However, that negative result does not necessarily apply to

"the case where the length of the longest path is already known to be" short.