8
$\begingroup$

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:

  1. Is this problem NP hard?

  2. 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}$.)

  3. 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?

$\endgroup$
6
  • 5
    $\begingroup$ I take it that your sets are exponentially large, i.e., "polynomial-time" means polynomial in $n$, $\log N$, and (?) $\log q$. Now, since the sets are too large to be given by a list of their elements, how are they presented to the algorithm? The problem is not well-defined without this information. $\endgroup$ Aug 3, 2011 at 15:19
  • $\begingroup$ @Emil: Good point. For the P vs NP version, how about if I give you three deterministic algorithms $F_A$, $F_B$, and $F_C$ that run in polynomial time, such that you can input an integer $0\le k<N$ and get back an element of $A$, $B$, and $C$, respectively. Does that suffice, or is there some further subtlety that I'm missing?/ Of course, the question of whether there is an algorithm that runs in time $O(N^{3/2-\epsilon})$ doesn't have this issue, since that gives plenty of time to list the three sets. $\endgroup$ Aug 3, 2011 at 17:35
  • $\begingroup$ @Joe, so the sets are essentially given in a succinct form (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, 2011 at 22:26
  • $\begingroup$ @Kaveh: I'm not familiar with this terminology of succinct form versus oracle 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 by succinct form? The input to the algorithm is the number $k$, and the output is an $n$-tuple of numbers in $\mathbb{F}_q$. $\endgroup$ Aug 3, 2011 at 22:39
  • $\begingroup$ It is very similar, the code of those algorithms given as circuits as inputs to the problem are called succinct input. What is not clear is the way we are given access to those algorithms, are they (i.e. the code of those algorithms) given to us as inputs? $\endgroup$
    – Kaveh
    Aug 4, 2011 at 15:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Ummm... Okay, thanks. But note that all three sets are required to have the same number of elements, as I specified in the statement of the problem. (I meant distinct elements, of course.) So how can you take $B$ and $C$ to be singletons? $\endgroup$ Aug 4, 2011 at 12:54
  • $\begingroup$ Oops, I missed that part. But it should be easy to fix - take the elements of B to be (1,...), one of them the all 1, the elements of C to be (2,..), one of them all 2, and then the elements of A to be again (1,..) unless it is a solution of the NP-hard problem, in which case it can be the all 0. Now collinearity can occur only with the all 0 point, so we are done as before. $\endgroup$
    – domotorp
    Aug 4, 2011 at 13:51
  • $\begingroup$ @domotorp: the way you described the fix there is always a collinear triple. But yes, something like that should work. $\endgroup$ Aug 5, 2011 at 10:25
  • $\begingroup$ Really, why? Note that we need one member from each of A, B and C. $\endgroup$
    – domotorp
    Aug 5, 2011 at 11:04
  • $\begingroup$ You take the all-1 vector in $B$, the all-2 vector in $C$, and the all-1 or all-0 (whichever is present) vector in A. All all-$x$ vectors are collinear. $\endgroup$ Aug 5, 2011 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.