Instinto Lógico

Recuerda que nadie debe pensar por tí.

P versus NP

P VS NPEs indudable que la complejidad computacional es una rama de las matemáticas/ informática que de suma importancia. Hay algunos problemas que son irresolubles por la gran cantidad de operaciones que se deberían realizar.

Cuando hacemos referencias a P y NP estamos haciendo referencia a la complejidad computacional.

Sin entrar engrandes disquisiciones matemáticas podemos definir varias clases de complejidad:

  • La clase P es el conjunto de todos los problemas resolubles en tiempo polinómico.
  • La clase EXP es el conjunto de todos los problemas resolubles en tiempo exponencial.
  • La clase PSPACE es el conjunto de todos los problemas resolubles en espacio polinómico.
  • La clase EXPSPACE es el conjunto de todos los problemas resolubles en espacio exponencial.

Por ejemplo el problema de determinar si un número es par o encontrar el camino más corto en un grafo se pueden resolver en tiempo y espacio polinómico, sin embargo muchos problemas sobre toma de decisiones o de combinatoria, como por ejemplo, el problema PERMUTACION: “dada una cadena de caracteres C sin caracteres repetidos, calcular todas las posibles permutaciones de los caracteres de C sólo se sabe resolver en tiempo exponencial en concreto n!

Formula de Stirling

Pero ¿a qué nos referimos cuando hablamos de NP?

Hasta ahora nos habíamos referido a la complejidad como el tiempo para resolver un problema pero nos planteamos lo siguiente: ¿Cuánto tiempo necesitamos para verificar que una solución dada a un problema es correcta? Comprobar una solución es una tarea más sencilla que calcularla y, por lo tanto, puede requerir menos recursos.

Para definir a qué nos referimos con verificar definimos el concepto de función verificadora:

Sea T un conjunto, los elementos del cual se llaman testigos. Dado un problema decisional Prob : I → {SI,NO}, una función verificadora ´ es una funcion´ v : I × T → {SI,NO} tal que:

  • Si Prob(x) = SI, entonces existe algún testigo ´ t ∈ T para el que v(x,t) = SI.
  • Si Prob(x) = NO, entonces v(x,t) = NO para cualquier t ∈ T .

Y así diremos que un problema es verificable en tiempo polinómico si tiene una función verificadora v calculable en tiempo polinomico.

La clase NP es el conjunto de todos los problemas verificables en tiempo polinómico.

Se ha demostrador que las clases de complejidad citadas satisfacen las siguientes relaciones:

  • P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ EXPSPACE
  • P ⊂ EXP
  • PSPACE ⊂ EXPSPACE

Últimamente se está investigando la relación entre las clases de complejidad P y NP por varios motivos:

A la clase NP pertenecen muchos problemas relevantes en varios ámbitos (logística, planificación, diseño asistido por computador, criptografía, . . . ).

El problema surge porque las matemáticas aún no son capaces de determinar si un problema es P o NP. Hay que desarrollar un algoritmo para resolver el problema y determinar la complejidad de dicho algoritmo y claro, dado un algoritmo no es posible saber si hay otro más eficiente que resuelve el mismo problema. Por tanto, no se ha conseguido demostrar la relación entre la clase P y la clase NP. Es decir, hay problemas que se pueden verificar en tiempo polinómico pero no sabemos si se pueden ´ resolver o no en tiempo polinómico.

NP representa una frontera de la tratabilidad. Los problemas que no pertenecen a NP son claramente intratables; si un problema no se puede verificar de una forma eficiente, parece lógico pensar que su resolución será intratable.

La relación entre las clases P y NP es uno de los problemas abiertos más importantes del campo de la informática teórica Como ya sabemos que P ⊆ NP, la duda está en si NP ´ ⊆ P.

Dicho de otra forma, nos preguntamos si podemos resolver en tiempo polinómico todos los problemas que se pueden ´ verificar en tiempo polinómico, es decir, si P ? = NP. Algunas formulaciones equivalentes de esta pregunta sería: • ¿Son tratables todos los problemas de NP? ¿Hay algún problema que esté en NP pero no en P?

Durante muchos años se ha intentado demostrar qué relación existe entre P y NP, pero no hay ninguna demostración aceptada, ni a favor ni en contra, sobre la inclusión o no inclusión de NP en P

Hoy en día parece que se tiende a apuntar a que P ≠ NP. Si se consigue demostrar que P ≠ NP no tendría consecuencias importantes en la concepción de la informática actual, pero si se llega a demostrar la igualdad, es casi seguro que entraremos en una revolución de la informática moderna; problemas que hasta ahora se consideran difíciles (que no se pueden tratar de una forma práctica) pasarían a poder resolverse de una forma eficiente.

Por poner un ejemplo, la criptografía de clave pública basa su seguridad en la existencia de problemas computacionalmente complejos verificables de forma eficiente. La existencia de algoritmos eficientes para resolver estos problemas reduciría enormemente el coste de descifrar cualquier mensaje, lo que comprometería la seguridad de los sistemas de seguridad basados en clave pública utilizados en la actualidad.

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme