3SUM y puntos colineales

El concepto de reducción se utiliza también para hablar de cotas inferiores que están en función de otras cotas inferiores que no son conocidas, pero sí muy estudiadas. Por ejemplo, si podemos reducir la multiplicación de matrices de $n \times n$ a un cierto problema $P$, sabemos que $P$ no es más fácil que multiplicar matrices. Antes de Strassen, podríamos haber pensado que la complejidad del problema era $\Theta(n^3)$. En 1969, Strassen mostró cómo multiplicar matrices en tiempo $O(n^{2.81})$, y luego en 1990 Coppersmith y Winograd lo redujeron a $O(n^{2.38})$ (analizado en 2014 por Le Gall).

No se conoce una cota inferior general para el problema más allá de la obvia $\Omega(n^2)$. Un problema tan trabajado es útil en sí mismo como cota inferior: si podemos resolver $P$ en menor tiempo, habremos encontrado un algoritmo para multiplicar matrices mejor que todos los conocidos. Decimos entonces que $P$ es multiplicación-de-matrices-hard. Tal como en la NP-completitud, donde se dice que un problema es NP-hard, es una forma de decir cuán improbable se considera obtener un mejor resultado para resolver $P$ (nota: ser NP-completo equivale a ser NP y ser NP-hard).

El problema 3SUM es el de, dados $n$ números reales $Z = \{ z_1, \ldots, z_n\}$, encontrar tres que sumen cero (pueden repetirse números en la suma). Veamos cómo resolver este problema en tiempo $O(n^2)$. Supongamos que primero ordenamos los números en tiempo $O(n\log n)$. Luego, tomaremos cada número $z_i$ y buscaremos dos números de $Z$ que sumen $- z_i$. Para ello, progresaremos desde las dos puntas del arreglo ordenado, $m \leftarrow z_1$ y $M \leftarrow z_n$, con dos cursores. Si $m+M+z_i < 0$, moveremos el cursor de la izquierda hacia adelante, $m \leftarrow z_2$. En cambio, si $m+M+z_i > 0$, moveremos el cursor de la derecha hacia atrás, $M \leftarrow z_{n-1}$. En todo momento, el invariante es que los números que ya dejamos de considerar no pueden formar parte de la solución, y se puede ver que se mantiene cuando movemos los cursores. Al final, en tiempo $O(n)$ encontramos un $m$ y $M$ adecuados (con lo cual resolvimos el problema con los números $m$, $M$ y $z_i$), o los cursores se cruzan y debemos pasar a considerar otro número $z_i$. El tiempo total es $O(n^2)$.

Por mucho tiempo se sospechó que $\Theta(n^2)$ era la complejidad del problema, pero en 2014 Grunlund y Pettie encontraron una solución de tiempo $O(n^2/(\log n / \log\log n)^{2/3})$. Aún así, se sospecha que el problema es $\Omega(n^{2-o(1)})$ (es decir, $\Omega(n^{1.999\ldots})$ para cualquier cantidad finita de $9$s). Como es un problema bastante estudiado, es interesante cuando se establece que otro problema es 3SUM-hard.

Consideremos el problema de, dados $n$ puntos $(x_i,y_i)$, encontrar tres puntos colineales que no estén en una línea vertical. Esta última restricción se pone por conveniencia para demostrar una cota inferior, pues ese subcaso es fácil de resolver.

Reduciremos 3SUM a este problema, para mostrar que es 3SUM-hard. Dados $n$ números $Z = \{ z_1, \ldots, z_n\}$, generaremos 3 puntos para cada $z_i$: $(1,z_i)$, $(2,-\frac{z_i}{2})$, y $(3,z_i)$. Veremos que este conjunto tiene 3 puntos colineales no en vertical sii $Z$ tiene 3 números que suman $0$. Dadas las coordenadas $x_i$ elegidas, estos 3 puntos colineales deben ser de la forma $(1,a)$, $(2,b)$ y $(3,c)$, con $b = \frac{a+c}{2}$. Pero como $a=z_i$ para algún $i$, $b = -\frac{z_j}{2}$ para algún $j$, y $c=z_k$ para algún $k$, tenemos que $-\frac{z_j}{2} = \frac{z_i+z_k}{2}$, de lo que se deduce que $z_i + z_j + z_k = 0$. También puede verse que ocurre lo recíproco: si hay tres números que sumen cero, hay tres puntos colineales. Como la conversión cuesta sólo $O(n)$, tenemos que el problema es 3SUM-hard.

Finalmente, el problema de encontrar tres puntos colineales sin la restricción de que estén en vertical también es 3SUM-hard. Para que esto tenga sentido, sin embargo, aún debemos prohibir que los puntos sean iguales, pues el problema es trivial en ese caso. Si los tres puntos deben ser distintos, entonces podemos crear los puntos $(z_i,z_i^3)$. Si aparecen tres puntos colineales distintos $(a,a^3)$, $(b,b^3)$ y $(c,c^3)$, con $a<b<c$, entonces tenemos que $\frac{a^3-b^3}{a-b} = \frac{b^3-c^3}{b-c}$, es decir, $a^2+ab+b^2 = b^2 + bc + c^2$, de donde tenemos $a^2-c^2 = -b(a-c)$, o $(a+c)(a-c) = -b(a-c)$. Dividiendo por $a-c$ obtenemos $a+b+c=0$.