Intuitivamente, un problema es reducible a un problema si las soluciones de existen y dan una solución para siempre que tenga solución. Así, resolver no puede ser más difícil que resolver . Normalmente, esto se expresa de la forma , y se añade un subíndice en para indicar el tipo de reducción utilizada. Por ejemplo, se usa la letra como subíndice para indicar que la reducción puede realizarse en tiempo polinomial: .
reducción, complejidad, teoría, computación, teoría, complejidad, computacional, reducción, transformación, problema, otro, problema, dependiendo, transformación, usada, reducción, puede, utilizar, para, definir, clases, complejidad, conjunto, problemas, ejemp. En teoria de la computacion y teoria de la complejidad computacional una reduccion es una transformacion de un problema a otro problema Dependiendo de la transformacion usada la reduccion se puede utilizar para definir clases de complejidad en un conjunto de problemas Ejemplo de reduccion de un problema de satisfacibilidad booleana a un problema de cobertura de vertices Los vertices azules forman una cobertura que se corresponde con los valores verdaderos Intuitivamente un problema A displaystyle A es reducible a un problema B displaystyle B si las soluciones de B displaystyle B existen y dan una solucion para A displaystyle A siempre que A displaystyle A tenga solucion Asi resolver A displaystyle A no puede ser mas dificil que resolver B displaystyle B Normalmente esto se expresa de la forma A B displaystyle A leq B y se anade un subindice en displaystyle leq para indicar el tipo de reduccion utilizada Por ejemplo se usa la letra p displaystyle p como subindice para indicar que la reduccion puede realizarse en tiempo polinomial A p B displaystyle A leq p B Vease tambien EditarDinamica de sistemas Pensamiento sistemico Azar Complejidad biologica Efecto mariposa Fractal Inteligencia artificial Problema del viajante Anexo Clases de complejidad Sistemas dinamicos Teoria del caos Teoria de sistemas Cibernetica Datos Q1197709 Obtenido de https es wikipedia org w index php title Reduccion complejidad amp oldid 124754790, wikipedia, wiki, leyendo, leer, libro, biblioteca,
