Reducción parsimoniosa

En la teoría de la complejidad computacional y la complejidad del juego , una reducción parsimoniosa es una transformación de un problema a otro (una reducción ) que preserva el número de soluciones. De manera informal, es una biyección entre los respectivos conjuntos de soluciones de dos problemas. Una reducción general de un problema a otro es una transformación que garantiza que siempre que tenga una solución también tenga al menos una solución y viceversa. Una reducción parsimoniosa garantiza que para cada solución de , existe una solución única de y viceversa. ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$ ${\ Displaystyle A}$ ${\ Displaystyle B}$

Las reducciones parsimoniosas se usan comúnmente en la complejidad computacional para probar la dureza de los problemas de conteo , para contar clases de complejidad como #P . Además, se utilizan en la complejidad del juego, como una forma de diseñar acertijos difíciles que tienen una solución única, como requieren muchos tipos de acertijos.

Sea una instancia de problema . Una reducción Parsimoniosa de un problema a otro es una reducción tal que el número de soluciones a es igual al número de soluciones al problema . ^[1] Si existe tal reducción, y si tenemos un oráculo que cuenta el número de soluciones de las cuales es una instancia de , entonces podemos diseñar un algoritmo que cuente el número de soluciones de , la instancia correspondiente de . En consecuencia, si contar el número de soluciones a las instancias de es difícil, contar el número de soluciones a debe serlo también. ${\ Displaystyle x}$ ${\ Displaystyle X}$ ${\ Displaystyle R}$ ${\ Displaystyle X}$ ${\ Displaystyle Y}$ ${\ Displaystyle x}$ ${\ Displaystyle R (x)}$ ${\ Displaystyle R (x)}$ ${\ Displaystyle Y}$ ${\ Displaystyle x}$ ${\ Displaystyle X}$ ${\ Displaystyle X}$ ${\ Displaystyle Y}$

Así como las reducciones muchos-uno son importantes para demostrar la completitud de NP , las reducciones parsimoniosas son importantes para demostrar la completitud para contar clases de complejidad como ♯P . ^[1] Debido a que las reducciones parsimoniosas conservan la propiedad de tener una solución única, también se utilizan en la complejidad del juego , para mostrar la dureza de acertijos como el sudoku , donde la singularidad de la solución es una parte importante de la definición del acertijo. ^[2]

Los tipos específicos de reducciones parsimoniosas pueden definirse por la complejidad computacional u otras propiedades del algoritmo de transformación. Por ejemplo, una reducción parsimoniosa en tiempo polinomial es aquella en la que el algoritmo de transformación toma tiempo polinomial . Estos son los tipos de reducción que se utilizan para demostrar ♯P-completitud . ^[1] En complejidad parametrizada , se utilizan reducciones parsimoniosas de FPT ; se trata de reducciones parsimoniosas cuya transformación es un algoritmo manejable de parámetros fijos y que asignan valores de parámetros acotados a valores de parámetros acotados mediante una función computable. ^[3]

Las reducciones parsimoniosas de tiempo polinómico son un caso especial de una clase más general de reducciones para problemas de conteo, las reducciones de conteo de tiempo polinomial . ^[4]