Tipos de reducciones y definiciones asociadas de dureza.

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 $A \leq B$$A$$B$$A$$M_{A}$$B$$O_{B}$

• Reducción de Turing: puede realizar múltiples consultas a . O $M_{A}$$O_{B}$

• 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 $O_{B}$$O_{B}$$P^{A} = P^{B}$

• 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 B ≤ $M_{A}$$O_{B}$$O_{B}$$\leq_{m}$

  $A \leq_{m} B$ si una función computable tal que .f : Σ ∗ → Σ ∗ f ( x ) ∈ $\exists$$f: \Sigma^{\ast} \to \Sigma^{\ast}$$f(x) \in B \iff x\in A$

• 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 $O_{B}$$\leq^{p}_{m}$

  $A \leq^p_{m} B$ si una función computable de tiempo múltiple tal que .$\exists$$f: \Sigma^{\ast} \to \Sigma^{\ast}$$f(x) \in B \iff x\in A$

• Reducción parsimoniosa: También llamado "tiempo polinómico uno-uno la reducción": reducción de A Cook donde cada instancia de $A$ mapeado a una instancia única de $B$ . Equivalente: ( $\leq^{p}_{1}$ denota reducción parsimoniosa)

  $A \leq^p_{1} B$ si $\exists$ una biyección computable de tiempo múltiple $f: \Sigma^{\ast} \to \Sigma^{\ast}$ tal que $f(x) \in B \iff x\in A$ .

  Estas reducciones preservan el número de soluciones. Por lo tanto, $\#M_{A} = \#O_{B}$ .

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.

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.$\mathsf{NP}$

¿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.$\mathsf{NP}$$\mathsf{NP}$

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

Tenga en cuenta que $\mathsf{\#P}$ 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.

$O_B$