4.4: Exacto versus Aproximado

Muchos problemas combinatorios admiten soluciones “exactas”, y en estos casos, generalmente nos esforzaremos por encontrarlas. El Teorema de Erdős/Szekeres de antes en este capítulo es un buen ejemplo de un resultado “exacto” . Con esta afirmación, queremos decir que para cada par\(m\) y\(n\) de enteros positivos, hay una secuencia de números reales\(mn\) distintos que no tiene ni una subsecuencia creciente de tamaño\(m+1\) ni una subsecuencia decreciente de tamaño\(n+1\). Para ver esto, considere la secuencia\(σ\) definida de la siguiente manera: Para cada uno\(i=1,2,…,m\), vamos\(B_i=\{j+(m−1)i:1≤j≤n\}\). Tenga en cuenta que cada uno\(B_i\) es un bloque de enteros\(n\) consecutivos. A continuación, definir una permutación\(σ\) de los primeros números enteros mn estableciendo\(\alpha<β\) si existen enteros distintos\(i_1\) y\(i_2\) así que\(\alpha \in B_{i1}\) y\(β \in B_{i2}\). Además, para cada uno\(i=1,2,…,m\), establezca\(\alpha <β\)\(σ\) cuándo\(1+(m−1)i≤β<\alpha ≤n+(m−1)i\). Claramente, cualquier subsecuencia creciente de\(σ\) contiene como máximo un miembro de cada bloque, por lo que no\(σ\) tiene una secuencia creciente de tamaño\(m=1\). Por otro lado, cualquier secuencia decreciente en\(σ\) está contenida en un solo bloque, por lo que no\(σ\) tiene secuencia decreciente de tamaño\(n+1\).

Como otro ejemplo de una solución exacta, el número de soluciones enteras a\(x_1+x_2+…x_r=n\) con\(x_i>0\) for\(i−1,2,…,r\) es exactamente\(C(n−1,r−1)\). Por otro lado, nada de lo que hemos discutido hasta ahora nos permite proporcionar una solución exacta para el número de particiones de un entero\(n\).

4.4.1 Soluciones aproximadas y asintóticas

Aquí hay un ejemplo de un problema famoso que solo podemos discutir en términos de soluciones aproximadas, al menos cuando el tamaño de entrada es adecuadamente grande. Para un entero\(n\), vamos\(\pi(n)\) denotar el número de primos entre los primeros enteros\(n\) positivos. Por ejemplo,\(\pi(12)=5\) ya que 2, 3, 5, 7 y 11 son primos. El valor exacto de\(\pi(n)\) se conoce cuando\(n≤10^{23}\), y de hecho:

\(\pi(10^{23})=1,925,320,391,606,803,968,923\)

Por otro lado, podría preguntarse si\(\pi(n)\) tiende al infinito a\(n\) medida que crece cada vez más. La respuesta es sí, y aquí hay un argumento sencillo y bastante clásico. Supongamos al contrario que sólo había\(k\) primos, donde\(k\) es un entero positivo. Supongamos que estos\(k\) primos se enumeran en orden creciente como\(p_1<p_2<⋯<p_k\), y considerar el número\(n=1+p_1p_2⋯p_k\). Entonces no\(n\) es divisible por ninguno de estos primos, y es mayor que\(p_k\), lo que implica que\(n\) es un número primo mayor que\(p_k\) o divisible por un número primo mayor que\(p_k\).

Entonces eso lo sabemos\(\lim_{n \rightarrow \infty} \pi(n)= \infty\). En una situación como esta, los matemáticos suelen querer saber más sobre qué tan rápido\(\pi(n)\) llega al infinito. Algunas funciones van al infinito “lentamente”, como\(\log ⁡n\) o\(\log⁡ \log ⁡n\). Algunos van al infinito rápidamente, como\(2n, n!\) o\(2^{2n}\). Ya que\(\pi(n)≤n\), no puede ir al infinito tan rápido como estas tres últimas funciones, pero podría ir al infinito como\(\log ⁡n\) o tal vez\(\sqrt{n}\).

A partir de resultados computacionales (hechos a mano, mucho antes de que existieran las computadoras), Legendre conjeturó en 1796 que\(\pi(n)\) va al infinito como\(n/ \ln⁡ n\). Para ser más precisos, conjeturó que

\(\displaystyle \lim_{n→∞} \dfrac{\pi(n) \ln⁡ n}{n}=1\).

En 1896, exactamente cien años después de la conjetura de Legendre, Hadamard y de la Vallée-Poussin publicaron de forma independiente pruebas de la conjetura, utilizando técnicas cuyas raíces están en la obra pionera de Riemann en análisis complejos. Este resultado, ahora conocido simplemente como el Teorema de los Números Primos, continúa siendo tema muy estudiado hasta el día de hoy en el límite del análisis y la teoría de números.

4.4.2 Algoritmos de Tiempo Polinomial

A lo largo de este texto, pondremos considerable énfasis en los problemas para los que se puede encontrar un certificado en tiempo polinómico. Esto se refiere a problemas para los cuales hay alguna constante\(c>0\) por lo que existe un algoritmo\(\mathcal{A}\) para resolver el problema que tiene tiempo de ejecución\(O(n^c)\) donde\(n\) está el tamaño de entrada. \(\mathcal{P}\)El símbolo sugiere polinomio.

4.4.3\(\mathcal{P} = \mathcal{N} \mathcal{P}\)?

Quizás la pregunta más famosa en el límite de las matemáticas combinatorias, la informática teórica y la lógica matemática es la cuestión notoriamente desafiante de decidir si\(\mathcal{P}\) es lo mismo que\(\mathcal{NP}\). Este problema tiene la forma taquigráfica:\(\mathcal{P}=\mathcal{NP}\)? Aquí, presentamos una breve discusión informal sobre este problema.

Primero, ya hemos introducido la clase\(\mathcal{P}\) que consiste en todos los problemas combinatorios sí-no que admiten algoritmos polinomiales de tiempo. Los dos primeros problemas discutidos en este capítulo pertenecen\(\mathcal{P}\) ya que pueden resolverse con algoritmos que tienen tiempo de ejecución\(O(n)\) y\(O(n^3)\), respectivamente. Además, al determinar si una gráfica es 2-colorable y si está conectada, ambos admiten algoritmos polinomiales de tiempo.

Debemos enfatizar que puede ser muy difícil determinar si un problema pertenece a clase\(\mathcal{P}\) o no. Por ejemplo, no vemos cómo dar un algoritmo rápido para resolver el tercer problema (suma de subconjunto), pero eso no significa que no haya uno. ¡Quizás todos necesitamos estudiar más duro!

Dejando ese tema a un lado por el momento, la clase\(\mathcal{NP}\) consiste en sí—no problemas para los cuales hay un certificado para una respuesta sí cuya corrección puede verificarse en tiempo polinómico. De manera más formal, a esto se le llama la clase de problemas polinomiales no deterministas del tiempo. Nuestro tercer problema definitivamente pertenece a esta clase.

La famosa pregunta es determinar si las dos clases son iguales. Evidentemente, algún problema al que pertenezca\(\mathcal{P}\) también pertenece\(\mathcal{NP}\), es decir\(\mathcal{P} \subseteq \mathcal{NP}\), ¿pero son iguales? Parece difícil creer que existe un algoritmo polinómico de tiempo para resolver el tercer problema (el problema de la suma de subconjuntos), y nadie se ha acercado a resolver este problema. Pero si tienes una buena idea, asegúrate de discutirla con uno o ambos autores de este texto antes de hacer pública tus noticias. Si resulta que tienes razón, seguro que atesorarás una oportunidad para tomar fotos con la tuya de verdad.