Reducció (complexitat)

En teoria de la computació i teoria de la complexitat computacional, una reducció és una transformació d'un problema a un atre problema. Depenent de la transformació usada, la reducció es pot utilisar per a definir classes de complexitat en un conjunt de problemes.

Eixemple de reducció d'un problema de satisfacibilidad booleana a un problema de cobertura de vèrtiços. Els vèrtiços blaus formen una cobertura que es correspon en els valors verdaders.

Intuitivamente, un problema $A$ és reducible a un problema $B$ si les solucions de $B$ existixen i donen una solució per a $A$ sempre que $A$ tinga solució. Aixina, resoldre $A$ no pot ser més difícil que resoldre $B$. Normalment, açò s'expressa de la forma $A\le B$, i s'afig un subíndex en $\le$ per a indicar el tipo de reducció utilisada. Per eixemple, s'usa la lletra $p$ com a subíndex per a indicar que la reducció pot realisar-se en temps polinomial: $A{\le }_{p}B$.

Vore també

• Dinàmica de sistemes
• Pensament sistémico
• Encert
• Complexitat biològica
• Efecte palometa
• Fractal
• Inteligència artificial
• Problema del viajante
• Anex:Classes de complexitat
• Sistemes dinàmics
• Teoria del caos
• Teoria de sistemes
• Cibernètica