control de lectura_capitulo 11 - Mauricio axel 20

Vista previa del material en texto

Lenguajes y autómatas 1 
INSTITUTO TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
Ingeniería en sistemas computacionales
Lenguajes y autómatas 1
Control de lectura 
11.- Otras clases de problemas
Profesor: Bedolla Solano Silvestre
López Anselmo Mauricio Axel 
CONTROL: 18320904
11.- Otras clases de problemas
Resumen.
Para integrar estos conceptos, consideremos la importante cuestión de probar que un número es primo.Muchos sistemas criptográficos actuales se basan en los dos puntos siguientes:1. La capacidad de descubrir rápidamente números primos grandes (para permitir la comunicación entre máquinas de una forma que no está sujeta a que un extraño intercepte el mensaje) y2. La suposición de que se tarda un tiempo exponencial en descomponer un entero en factores, si el tiempo se mide como una función de la longitud n del entero escrito en binario.Veremos que la comprobación de si un número es primo o no está tanto enNPcomo en co-NP, y por tanto no es probable que podamos demostrar que el problema de decidir si un número es primo o no sea NP-completo. Esto es lamentable, ya que las demostraciones de que los problemas son NP-completos son las más comunes para demostrar que un problema probablemente requiere un tiempo exponencial. También veremos la comprobación de si un número es primo o no pertenece a la clase RP. Esta situación es positiva por un lado, pero negativa por otro. Es buena, porque en la práctica, los sistemas criptográficos que requieren determinar si los números son primos o no realmente emplean un algoritmo de la clase RP para encontrarlos. Pero es mala porque refuerza la suposición de que no seremos capaces de demostrar que el problema de que un número sea primo o no es NP-completo.
Complementarios de los lenguajes de NP
La clase de lenguajes P es cerrada para la complementación .Veamos por qué con un sencillo argumento: sea L un lenguaje de P y sea M una máquina de Turing para L. Modificamos M como sigue, con el fin de aceptar L. Introducimos un nuevo estado de aceptación q y obtenemos la nueva transición de la MT a q cuando M se para en un estado que no es de aceptación. Hacemos también que los anteriores estados de aceptación de M dejen de serlo. Entonces la MT modificada acepta L, y opera en el mismo tiempo que lo hace M, con la posible adición de un movimiento. Por tanto, L pertenece a P si L pertenece. No se sabe si N Pes cerrada para la complementación. Parece ser que no, sin embargo, es de esperar que cuando un lenguaje L es NP-completo, entonces su complementario no pertenece a NP.
Bibliografías.
2008 por PEARSON EDUCACIÓN S.A.Ribera del Loira, 2828042 Madrid
Introducción a la teoría de autómatas, lenguajes y computaciónHopcroft, J. E.; Motwani, R.; Ullman, J. D.
Página 1 | 1
Acapulco Gro. 16 de diciembre de 2020