Reducción (complejidad)

Reducción (complejidad)

Reducción (complejidad)

Ejemplo de reducción de un problema de satisfacibilidad booleana a un problema de cobertura de vértices. Los vértices azules forman una cobertura que se corresponde con los valores verdaderos.

En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada se puede utilizar para definir clases de complejidad en un conjunto de problemas. Intuitivamente, un problema A es reducible a un problema B si las soluciones de B existen y dan una solución de A siempre que A tenga solución. Así, resolver A no puede ser más difícil que resolver B. Normalmente, escribimos A ≤ B, con un subíndice en ≤ para indicar el tipo de reducción utilizada.

Obtenido de "Reducci%C3%B3n (complejidad)"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Complejidad irreducible — Existen desacuerdos sobre la neutralidad en el punto de vista de la versión actual de este artículo o sección. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

  • NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   Wikipedia Español

  • NP (clase de complejidad) — En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ( tiempo polinomial no determinista ). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Emergencia (filosofía) — Para otros usos de este término, véase Emergencia (desambiguación). La emergencia o surgimiento hace referencia a aquellas propiedades o procesos de un sistema no reducibles a las propiedades o procesos de sus partes constituyentes. El concepto… …   Wikipedia Español

  • Anexo:Sesgos cognitivos — El hombre en el centro ha cometido un error en sus pasos de baile, y choca contra la mujer, que se enoja y los demás murmuran. En la obra de Jane Austen Orgullo y prejuicio (1813) se muestra claramente el prejuicio de clases sociales y cómo el… …   Wikipedia Español

  • Horario de verano — Artículo principal: Huso horario Véase también: Horario de verano en el mundo …   Wikipedia Español

  • Saab 39 Gripen — La exactitud de la información en este artículo o sección está discutida. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Gobernanza ambiental — La gobernanza ambiental es el gobierno y administración del medio ambiente y los recursos naturales desde su consideración como un bien común mundial, de la categoría específica de los que se dividen al compartirse.[1] El carácter mundial de… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”