Reducción parsimoniosa - Parsimonious reduction

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 definen para problemas en clases de complejidad no determinista como NP , que contiene problemas cuyas soluciones candidatas pueden ser verificadas por una máquina de Turing polinomial determinista en el tiempo .

Definicion formal

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 . Si existe tal reducción, y si tenemos un oráculo que cuenta el número de soluciones de las 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 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}$

Aplicaciones

Así como las reducciones de 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 . 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 los rompecabezas como el sudoku, donde la singularidad de la solución es una parte importante de la definición del rompecabezas.

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 polinómico 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 . 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.

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 polinómico .

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 ay el conjunto de soluciones que garantiza que el número de soluciones para ambos problemas es el mismo. ${\ Displaystyle R}$${\ Displaystyle x}$${\ Displaystyle R (x)}$

Ejemplos de reducción parsimoniosa en demostrar # P-completitud

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 pide el número de soluciones al problema. Los ejemplos de # P-completitud a continuación se basan en el hecho de que #SAT es # P-completo. ${\ Displaystyle x}$${\ Displaystyle X,}$${\ Displaystyle \ #x}$${\ Displaystyle x.}$

# 3SAT

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 correspondiente fórmula 3-CNF, 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 están contando equivalentes, y # 3SAT es # P-complete también.

Planar # 3SAT

Esta es la versión de conteo de Planar 3SAT. La reducción de dureza de 3SAT a Planar 3SAT dada por Lichtenstein tiene la propiedad adicional de que por cada asignación válida de una instancia de 3SAT, existe una asignación válida única de la correspondiente instancia de Planar 3SAT, y viceversa. Por lo tanto, la reducción es parsimoniosa y, en consecuencia, Planar # 3SAT es # P-completo.

Ciclo hamiltoniano

La versión de conteo de este problema pide el número de ciclos hamiltonianos en una gráfica dirigida dada . Seta Takahiro proporcionó una reducción de 3SAT a este problema cuando se restringió a gráficos de grado 3 máximos dirigidos en plano. La reducción proporciona una biyección entre las soluciones de una instancia de 3SAT y las soluciones de una instancia de Hamiltonian Cycle en gráficos de grado máximo de grado 3 dirigidos planar. Por lo tanto, la reducción es parsimoniosa y el ciclo hamiltoniano en gráficos de grado máximo 3 dirigidos planar es # P-completo. En consecuencia, la versión general del problema del ciclo hamiltoniano también debe ser # P-completo.

Shakashaka

Shakashaka es un ejemplo de cómo la reducción parsimoniosa podría usarse para mostrar la dureza de los acertijos lógicos. La versión de decisión de este problema pregunta si existe una solución para una instancia determinada del rompecabezas. La versión de conteo pregunta por el número de soluciones distintas a tal problema. La reducción de Planar 3SAT dada por Demaine, Okamoto, Uehara y Uno también proporciona una biyección entre el conjunto de soluciones a una instancia de Planar 3SAT y el conjunto de soluciones a la instancia correspondiente de Shakashaka. Por lo tanto, la reducción es parsimoniosa y la versión de conteo de Shakashaka es # P-completa.

Referencias