Reducción (teoría de la complejidad computacional)
La reducción en la teoría de la complejidad computacional es la transformación de un problema en otro. En general, para un algoritmo que convierte instancias de un problema en instancias de un problema que tienen la misma respuesta ("sí" o "no"), se dice que se reduce a , por lo que la reducibilidad es la relación entre dos problemas. Con la ayuda de tal conexión, se puede probar la computabilidad del problema o su pertenencia a una u otra clase de complejidad .
Algunos tipos de información: Reducción de Cooke , Reducción de Karp , Reducción de Levin , Reducción de Turing . La reducción de Turing es la forma más general de reducción: algún algoritmo (computable en una máquina de Turing ) se puede llamar cualquier número de veces, y cada llamada se considerará como un paso del algoritmo; para definir formalmente la reducibilidad de Turing, se utiliza el concepto de una máquina de Turing con un oráculo .
Literatura
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .