Partitioning a set based on binary predicate
There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$.  One can prove this with an adversarial argument.

Consider running the algorithm on the following input:


Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$.


Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on before it terminates.  If the running time of the algorithm is is $o(N^2)$, then for some sufficiently large $N$ the algorithm must make strictly fewer than $N^2-N$ queries to $F$, so there must be some pair of objects that it doesn't evaluate $F$ on, say $F(x_3,x_7)$.  But then consider running the algorithm on the following input:


Input #2: Same as input #1, except that $F(x_3,x_7)=1$.


Since the algorithm does not evaluate $F(x_3,x_7)$, the algorithm cannot distinguish these two inputs, and must produce the same output on Input #1 and Input #2.  However, the correct answer is different for these two inputs.  This means that the algorithm's output will be incorrect for at least one of these two inputs.

Therefore, any deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$ is not correct on all inputs.