En teoría de complejidad computacional y complejidad de juegos , 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 , exista una solución única de y viceversa.
Las reducciones parsimoniosas se utilizan habitualmente en la complejidad computacional para demostrar la dificultad de los problemas de conteo , para clases de complejidad de conteo como #P . Además, se utilizan en la complejidad de los juegos, como una forma de diseñar acertijos difíciles que tengan una solución única, como lo requieren muchos tipos de acertijos.
Sea una instancia del problema . Una reducción parsimoniosa de un problema a otro es una reducción tal que el número de soluciones de es igual al número de soluciones del problema . [1] Si existe dicha reducción, y si tenemos un oráculo que cuenta el número de soluciones de que 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 de las instancias de es difícil, entonces contar el número de soluciones de también debe ser difícil.
Así como las reducciones de muchos-uno son importantes para probar la completitud NP , las reducciones parsimoniosas son importantes para probar la completitud para contar clases de complejidad como #P . [1] Debido a que las reducciones parsimoniosas preservan la propiedad de tener una solución única, también se utilizan en la complejidad del juego , para mostrar la dificultad de los rompecabezas como el sudoku, donde la unicidad de la solución es una parte importante de la definición del rompecabezas. [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 de tiempo polinomial es aquella en la que el algoritmo de transformación toma un tiempo polinomial . Estos son los tipos de reducción que se utilizan para demostrar la #P-Completitud . [1] En la complejidad parametrizada , se utilizan reducciones parsimoniosas FPT ; estas son reducciones parsimoniosas cuya transformación es un algoritmo manejable con parámetros fijos y que asigna valores de parámetros acotados a valores de parámetros acotados mediante una función computable. [3]
Las reducciones parsimoniosas en tiempo polinomial son un caso especial de una clase más general de reducciones para problemas de conteo: las reducciones de conteo en tiempo polinomial . [4]
Una técnica común utilizada para demostrar que una reducción es parsimoniosa es mostrar que existe una biyección entre el conjunto de soluciones de y el conjunto de soluciones de que garantiza que el número de soluciones de ambos problemas sea el mismo.
La clase #P contiene las versiones de conteo de problemas de decisión NP. Dada una instancia de un problema de decisión NP, el problema solicita la cantidad de soluciones al problema. Los ejemplos de #P-completitud a continuación se basan en el hecho de que #SAT es #P-completo.
Esta es la versión de conteo de 3SAT . Se puede demostrar que cualquier fórmula booleana se puede reescribir como una fórmula en forma 3 - CNF . Cualquier asignación válida de una fórmula booleana es una asignación válida de la fórmula 3-CNF correspondiente, y viceversa. Por lo tanto, esta reducción conserva el número de asignaciones satisfactorias y es una reducción parsimoniosa. Entonces, #SAT y #3SAT son equivalentes de conteo, y #3SAT también es #P-completo.
Esta es la versión de conteo de Planar 3SAT. La reducción de dureza de 3SAT a Planar 3SAT dada por Lichtenstein [5] tiene la propiedad adicional de que para cada asignación válida de una instancia de 3SAT, existe una asignación válida única de la instancia correspondiente de Planar 3SAT, y viceversa. Por lo tanto, la reducción es parsimoniosa y, en consecuencia, Planar #3SAT es #P-completo.
La versión de conteo de este problema solicita la cantidad de ciclos hamiltonianos en un grafo dirigido dado . Seta Takahiro proporcionó una reducción [6] de 3SAT a este problema cuando se restringe a grafos dirigidos planares de grado 3 máximo. La reducción proporciona una biyección entre las soluciones a una instancia de 3SAT y las soluciones a una instancia de Ciclo hamiltoniano en grafos dirigidos planares de grado 3 máximo. Por lo tanto, la reducción es parsimoniosa y el Ciclo hamiltoniano en grafos dirigidos planares de grado 3 máximo es #P-completo. En consecuencia, la versión general del problema del Ciclo hamiltoniano también debe ser #P-completo.
Shakashaka es un ejemplo de cómo se podría utilizar la reducción parsimoniosa para demostrar la dificultad de los problemas lógicos. La versión de decisión de este problema pregunta si existe una solución para una instancia dada del problema. La versión de conteo pregunta por el número de soluciones distintas para tal problema. La reducción de Planar 3SAT dada por Demaine, Okamoto, Uehara y Uno [7] también proporciona una biyección entre el conjunto de soluciones para una instancia de Planar 3SAT y el conjunto de soluciones para la instancia correspondiente de Shakashaka. Por lo tanto, la reducción es parsimoniosa y la versión de conteo de Shakashaka es #P-completa.
