Finding colinear points in F_q^n

2011-08-03T15:10:39Z

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?

Answer by domotorp for Finding colinear points in F_q^n

2011-08-04T12:20:02Z

The problem is NP-hard if your sets are represented by functions as you describe in your comment. This is because you can encode some NP-hard problem with $F_A$. Suppose that $B$ and $C$ are both singletons. Let $F_A(k)$ return a point not on the $BC$ line if $k$ is not the solution of some NP-hard problem and a point on the $BC$ line if it is. This way there are three collinear points if and only if the NP-hard problem has a solution.

This also shows that the related (easier?) version is also NP-hard.

Finding colinear points in F_q^n - MathOverflow

Finding colinear points in F_q^n

Answer by domotorp for Finding colinear points in F_q^n