Finding colinear points in F_q^n - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T13:09:03Z http://mathoverflow.net/feeds/question/71999 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71999/finding-colinear-points-in-f-qn Finding colinear points in F_q^n Joe Silverman 2011-08-03T15:10:39Z 2011-08-04T12:20:02Z <p>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.</p> <p>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:</p> <ol> <li><p>Is this problem NP hard? </p></li> <li><p>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}$.) </p></li> <li><p>Or am I missing something and there's an obvious polynomial-time algorithm to solve this problem?</p></li> </ol> <p>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.</p> <p>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$.</p> <p>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?</p> http://mathoverflow.net/questions/71999/finding-colinear-points-in-f-qn/72082#72082 Answer by domotorp for Finding colinear points in F_q^n domotorp 2011-08-04T12:20:02Z 2011-08-04T12:20:02Z <p>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.</p> <p>This also shows that the related (easier?) version is also NP-hard.</p>