Límites criptografia

Tema elegido:
Los límite de la computación cuántica, S. Aaronson, Invetigación y Ciencia (mayo 208)

1/7

INTRODUCIÓN Para poder entender este articulo voy a poner una breve biografía del autor como de ciertas definiciones a tener en cuenta, lo cual creo que hará sin duda una mejor comprensión y seguimiento del mismo. BIOGRAFÍA Scott Aaronson Joel,nacido el 21 de mayo de 1981, licenciadoen ciencias de la computación por la Universidad de Cornell y doctorado por la Universidad de Berkeley en 2004 es actualmente profesor en la Ingeniería Eléctrica y Ciencias de la Computación en el instituto Tecnológico de Massachusetts Después de postdoctorados en el Instituto de Estudios Avanzados y la Universidad de Waterloo. tomó una posición en la facultad en el MIT en 2007, donde su principalárea de investigación es la computación cuántica y la teoría de la complejidad computacional en general. Fundador de la wiki (enciclopedia libre) Complejidad de Zoo, que cataloga todas las clases de complejidad computacional. Tras esto solo reseñar que tan joven científico de la computación teórica (solo dos años mas mayor que el que escribe) es una persona bastante cualificada para expresar unaopinión respetada en criptografía cuántica. DEFINICIONES Problemas de clase P Conocidos por ser muchos naturales, incluyendo las versiones de decisión de programa lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima. Algunos problemas naturales son completos para P, incluyendo la accesibilidad en grafos no dirigidos. Los problemas con mas dificultad en P son los problemasP-completos. Otra generalización de P es el tiempo polinómico no uniforme, si un problema esta en tiempo polinómico no uniforme puede solucionarse en un tiempo polinomial. Los algoritmos de tiempo polinómico son cerrados respecto a la composición. Esto lo que quiere decir que si uno escribe una función con un determinado tiempo polinómico y consideramos que las llamadas a esa misma función sonconstantes y, de tiempo polinómico, entonces el algoritmo completo es de tiempo polinómico. Esto es uno de los motivos principales por los que P se considera una máquina independiente; algunos rasgos de esta máquina, como el acceso aleatorio, es que puede calcular en tiempo polinómico el tiempo polinómico del algoritmo principal reduciéndolo a una máquina más básica. 2/7

Se conoce que algunosproblemas son resolubles en tiempo polinómico, pero no se conoce ningún algoritmo concreto para solucionarlos, ejemplos de ello pueden ser la búsqueda del camino mínimo desde un vértice inicial al resto de ellos o el de encontrar un ciclo que pase por cada arista de un grafo una sola vez. Estos algoritmos son expuestos y analizados en la asignatura de algorítmica y complejidad de ambos grados,Ingeniería del software e Ingeniería de Computadores de la Escuela Universitaria de informática de la Universidad Politécnica de Madrid. Problemas de clase NP Son aquellos que tienen un testigo polinómico para todas las instancias cuya respuesta es correcta. La única forma de que tengan un tiempo polinomial es realizando una etapa aleatoria, incluyendo el azar de alguna manera para elegir una posiblesolución, y entonces en etapas posteriores comprueba si esa solución es correcta. En otras palabras, dada una solución para una cierta instancia, es posible comprobar que es válida fácilmente y verificarla en tiempo polinómico.

Problemas de clase NP-Completos Los problemas de NP-completos son los problemas más difíciles de NP, en el sentido de que son los más probables de no encontrarse en P.Los problemas de NP-completos son esos problemas NPduros que están contenidos en NP, donde los problemas NP-duros son estos que cualquier problema en NP puede ser reducido a complejidad polinomial. Por ejemplo, la decisión del problema del viajante (básicamente lo que puede hacer un GPS) es NPcompleto, así que cualquier caso de cualquier problema en NP puede ser transformado mecánicamente en un...