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?

succinctform (i.e. the code of a circuit computing the characteristic function of the set), and not as oracles for the characteristic function of the sets. $\endgroup$ – Kaveh Aug 3 '11 at 22:26succinct formversusoracle for the characteristic function. As I said, I don't actually work in complexity theory. But the functions $F_A,F_B,F_C$ are given by an algorithm which could be implemented with $O(n(\log N)(\log q))^e$ gates, where $e$ would be some small number (say 10, to be on the safe side), and the big-$O$ constant is absolute. Is that what you mean bysuccinct form? The input to the algorithm is the number $k$, and the output is an $n$-tuple of numbers in $\mathbb{F}_q$. $\endgroup$ – Joe Silverman Aug 3 '11 at 22:391more comment