Tipos de reducciones y definiciones asociadas de dureza.

15

Sea A reducible a B, es decir, . Por lo tanto, la máquina de Turing aceptar tiene acceso a un oráculo de . Deje que la máquina de Turing que acepta sea y el oráculo para sea . Los tipos de reducciones:A B A M A B O BABABAMABOB

  • Reducción de Turing: puede realizar múltiples consultas a . O BMAOB

  • Reducción de Karp: también llamada "tiempo polinomial Reducción de Turing": la entrada a debe construirse en polytime. Además, el número de consultas a debe estar limitado por un polinomio. En este caso: . O B P A = P BOBOBPA=PB

  • Reducción de Turing de muchos: solo puede realizar una consulta a , durante el último paso. Por lo tanto, la respuesta del oráculo no se puede modificar. Sin embargo, el tiempo necesario para construir la entrada a no necesita estar limitado por un polinomio. Equivalente: ( denota una reducción de muchos) O B O BmMAOBOBm

    AmB si una función computable tal que .f : Σ Σ f ( x ) Bf:ΣΣf(x)BxA

  • Reducción de cocción: también llamada "reducción polinomial de tiempo múltiple": una reducción múltiple donde el tiempo necesario para construir una entrada a debe estar limitado por un polinomio. Equivalentemente: ( denota una reducción de muchos)p mOBmpag

    UNmetropagsi si una función computable de tiempo múltiple tal que .F:ΣΣF(X)siXUN

  • Reducción parsimoniosa: También llamado "tiempo polinómico uno-uno la reducción": reducción de A Cook donde cada instancia de UN mapeado a una instancia única de si . Equivalente: ( 1pag denota reducción parsimoniosa)

    UN1pagsi si una biyección computable de tiempo múltiple F:ΣΣ tal que F(X)siXUN .

    Estas reducciones preservan el número de soluciones. Por lo tanto, # #METROUN=# #Osi .

Podemos definir más tipos de reducciones al delimitar el número de consultas de oráculo, pero omitiéndolas, ¿alguien podría decirme amablemente si obtuve la nomenclatura de los diferentes tipos de reducciones utilizadas, correctamente? ¿Se definen los problemas de NP completo con respecto a la reducción de Cook o la reducción parsimoniosa? ¿Alguien puede dar un ejemplo de un problema que es NP-complete bajo Cook y no bajo reducción parsimoniosa.

Si no me equivoco, la clase # P-Complete se define con respecto a las reducciones de Karp.

Pavithran Iyer
fuente

Respuestas:

7

Su definición de reducciones parsimoniosas es incorrecta. Lo estás confundiendo con reducciones uno a uno en tiempo polinómico, que es un caso especial de reducciones de Karp. No conservan el número de "soluciones". Consulte esta respuesta para obtener más información sobre las reducciones teniendo en cuenta la cantidad de certificados.

El resto parece estar bien, aunque generalmente es mejor verlos en un gráfico bidimensional:

  • La complejidad de la reducción: computable, tiempo polinómico, espacio logarítmico, etc.
  • tipo de acceso: Turing, muchos uno, uno, etc.

¿Se definen los problemas de NP completo con respecto a la reducción de Cook o la reducción parsimoniosa?

dureza y la integridad de N P se definen con reducciones de Karp wrt (polytime muchos-uno), no Cook ni reducciones parsimoniosas.nortePAG

¿Alguien puede dar un ejemplo de un problema que es NP-complete bajo Cook y no bajo reducción parsimoniosa.

Tome el complemento de SAT, está completo para bajo las reducciones de Cook, no se cree que esté completo para N P bajo las reducciones de Karp. Las reducciones de Karp incluyen reducciones polytime one-one.nortePAGnortePAG

la clase # P-Complete se define con respecto a las reducciones de Karp

Tenga en cuenta que # #PAG no es una clase de problemas de decisiones, es una clase de problemas de cálculo de funciones. Su dureza e integridad generalmente se definen con reducciones de cocción (polytime Turing). Ver, por ejemplo, Arora y Barak, página 346.

Kaveh
fuente
Lo siento, parece que he intercambiado la terminología de "reducción de Karp" y "reducción de Cook". Si lo intercambio, entonces coincide con sus respuestas. Gracias. Con respecto a las reducciones parsimoniosas, ¿está diciendo que no conservan el número de "soluciones"? Si es así, veo en el Teorema 17.10 de Arora y Barak (Página 299) que las reducciones parsimoniosas realmente preservan el número de soluciones. Otra referencia: ( cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf )
Pavithran Iyer
Aquí dice una reducción parsimoniosa de L a SAT, asigna cada instancia x de L a una instancia única de SAT (es decir, el mapa de reducción es uno a uno): [ cse.cuhk.edu.hk/~andrejb/csc5170/notes /10L10.pdf] . ¿No es correcto suponer que si el número de soluciones se conserva mediante una reducción, entonces el mapa es uno?
Pavithran Iyer
@Pavithran, lo que escribiste en tu pregunta no era la definición de reducciones parsimoniosas. Para la respuesta, vea el ejercicio 2.13 en su libro.
Kaveh
0

Osi

Björn Lindqvist
fuente
Específicamente, se han cambiado las definiciones de las reducciones de Cook y Karp.
David Richerby