Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,B,C$ be subsets of $\mathbb{F}_q^n$ each containing $N$ points. How hard is it to determine if there is a triple $(a,b,c)\in A\times B\times C$ such that $a$, $b$, and $c$ are colinear? More specifically:
Is this problem NP hard?
Is there an algorithm to solve the problem in time $O(N^\kappa)$ for some small $\kappa$? (I'd be especially interested if $\kappa$ is strictly smaller than $\frac{3}{2}$.)
Or am I missing something and there's an obvious polynomial-time algorithm to solve this problem?
Note that the decision problem and the computational problem are polynomial-time equivalent. Thus suppose you can solve the decision problem in time $F(N)$. Write $$ A=A_1\cup A_2,\quad B=B_1\cup B_2,\quad C=C_1\cup C_2 $$ and solve the decision problem for the 8 sets $A_i\times B_j\times C_k$. That takes time $8F(N/2)$. If any of the decision problems returns a YES answer, then repeat the process with that particular $A_i,B_j,C_k$. After about $\log_2(N)$ iterations, you'll be down to sets containing only one element, which gives the colinear triple.
The case I'm most interested in is $n=2$. Obviously there are various generalizations, for example one could take $t$ sets and ask if there is a $t$-tuple lying in a linear space of dimension $t-2$.
One final related (easier?) question. If $A,B,C$ are simply taken to be subsets of $\mathbb{F}_q$, how difficult is it to determine if there is a triple $(a,b,c)$ satisfying $a+b+c=0$? There are obvious collision algorithms, but are there better algorithms?