Reducción de conteo de tiempo polinomial

---

En la teoría de la complejidad computacional de los problemas de conteo , una reducción de conteo de tiempo polinomial es un tipo de reducción (una transformación de un problema a otro) que se usa para definir la noción de completitud para la clase de complejidad ♯P . ^[1] Estas reducciones también pueden denominarse reducciones polinómicas de conteo de muchos a uno o reducciones débilmente parsimoniosas ; son análogas a las reducciones de muchos a uno para problemas de decisión y generalizan las reducciones parsimoniosas . ^[2]

Una reducción de conteo de tiempo polinomial generalmente se usa para transformar instancias de un problema difícil conocido en instancias de otro problema que se probará como difícil. Consta de dos funciones y , ambas deben ser computables en tiempo polinomial . La función transforma entradas para en entradas para y la función transforma salidas para en salidas para . ^{[1] [2]}${\displaystyle X}$${\displaystyle Y}$${\displaystyle f}$${\displaystyle g}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle g}$${\displaystyle Y}$${\displaystyle X}$

Estas dos funciones deben preservar la corrección de la salida. Es decir, supongamos que uno transforma una entrada para el problema en una entrada para el problema , y luego se resuelve para producir una salida . Debe darse el caso de que la salida transformada sea ​​la salida correcta para la entrada original . Es decir, si las relaciones entrada-salida de y se expresan como funciones, entonces la composición de su función debe obedecer a la identidad . Alternativamente, expresado en términos de algoritmos , un posible algoritmo para resolver sería aplicar para transformar el problema en una instancia de${\displaystyle x}$${\displaystyle X}$${\displaystyle y=f(x)}$${\displaystyle Y}$${\displaystyle y}$${\displaystyle z}$${\displaystyle g(z)}$${\displaystyle x}$${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle X=g\circ Y\circ f}$${\displaystyle X}$${\displaystyle f}$${\displaystyle Y}$, resuelva esa instancia y luego aplique para transformar la salida de en la respuesta correcta para . ^{[1] [2]}${\displaystyle g}$${\displaystyle Y}$${\displaystyle X}$

Como caso especial, una reducción parsimoniosa es una transformación de tiempo polinómico en las entradas de los problemas que conserva los valores exactos de las salidas. Tal reducción se puede ver como una reducción de conteo de tiempo polinomial, usando la función de identidad como la función . ^{[1] [2]}${\displaystyle f}$${\displaystyle g}$

---