Reducción de conteo en tiempo polinomial

En la teoría de la complejidad computacional de los problemas de conteo , una reducción de conteo en tiempo polinomial es un tipo de reducción (una transformación de un problema a otro) que se utiliza para definir la noción de completitud para la clase de complejidad ♯P . ^{[ 1 ]} Estas reducciones también pueden denominarse reducciones de conteo polinomiales 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 en tiempo polinomial se utiliza habitualmente para transformar instancias de un problema conocido y difícil.${\displaystyle X}$en instancias de otro problema${\displaystyle Y}$Eso está por demostrarse que es difícil. Consta de dos funciones.${\displaystyle f}$y${\displaystyle g}$, ambas deben ser computables en tiempo polinomial . La función${\displaystyle f}$transforma entradas para${\displaystyle X}$en entradas para${\displaystyle Y}$y la función${\displaystyle g}$transforma salidas para${\displaystyle Y}$en salidas para${\displaystyle X}$. ^{[ 1 ] [ 2 ]}

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

Como caso especial, una reducción parsimoniosa es una transformación de tiempo polinomial.${\displaystyle f}$en las entradas de los problemas que preserva los valores exactos de las salidas. Dicha reducción puede verse como una reducción de conteo en tiempo polinomial, utilizando la función identidad como la función${\displaystyle g}$. ^{[ 1 ] [ 2 ]}

Un problema funcional (especificado por sus entradas y salidas deseadas) pertenece a la clase de complejidad ♯P si existe una máquina de Turing no determinista que se ejecuta en tiempo polinomial, cuya salida al problema es el número de caminos de aceptación de la máquina de Turing. Intuitivamente, tales problemas cuentan el número de soluciones a problemas en la clase de complejidad NP . Un problema funcional${\displaystyle Y}$Se dice que es ♯P-difícil si existe una reducción de conteo en tiempo polinomial a partir de cada problema.${\displaystyle X}$en ♯P a${\displaystyle Y}$. Si, además,${\displaystyle Y}$en sí pertenece a ♯P, entonces${\displaystyle Y}$Se dice que es ♯P-completa . ^{[ 1 ] [ 2 ]} (A veces, como en el artículo original de Valiant que demuestra la completitud del permanente de matrices 0-1 , se utiliza una noción más débil de reducción, la reducción de Turing , para definir la ♯P-completitud. ^{[ 3 ]} )

El método habitual para demostrar un problema${\displaystyle Y}$En ♯P, ser ♯P-completo significa comenzar con un único problema conocido que sea ♯P-completo.${\displaystyle X}$y encontrar una reducción de conteo en tiempo polinomial a partir de${\displaystyle X}$a${\displaystyle Y}$. Si existe esta reducción, entonces existe una reducción de cualquier otro problema en ♯P a${\displaystyle Y}$, obtenido componiendo una reducción del otro problema a${\displaystyle X}$con la reducción de${\displaystyle X}$a${\displaystyle Y}$. ^{[ 1 ] [ 2 ]}