Hacer muchas reducciones y las reducciones de Turing definen el mismo NPC de clase

11

Me pregunto si las clases de NPC definidas por muchas reducciones y las reducciones de Turing son iguales.

Editar: Otra pregunta, ¿las reducciones de Turing solo están colapsando las clases C y co-C para algunos C o hay una clase , ya que existe un problema que no está en bajo la reducción de Karp y que está en bajo la reducción de Turing ?CC∪co−CC

cc.complexity-theory np-hardness reductions Ludovic Patey
fuente
44
¿Has leído en.wikipedia.org/wiki/… ?
Jukka Suomela
Gracias por tu enlace. Responde a la primera parte de mi pregunta, pero no responde si hay problemas que no están en co-C bajo la reducción de muchos y están en C bajo la reducción de Turing, para cualquier C.
Ludovic Patey
1
Lo sentimos, esta puede parecer una pregunta elemental o tal vez no estoy pensando bien a estas horas, pero me falta algo en el artículo de la wiki. El artículo dice que bajo las reducciones de Cook, NP-complete es igual a co-NP-complete, pero no lo veo. NP-hard es igual a co-NP-hard wrt Reducciones de cocción, pero NP-complete significa ser NP-hard y NP , y no veo por qué (por ejemplo) TAUT estaría en NP? Es decir, TAUT es co-NP-hard bajo las reducciones de Cook, pero eso no es suficiente para ser NP-complete.
Kaveh
@ Mononoid, debe reformular su pregunta para reflejar esta aclaración. Como tal, la pregunta es ambigua
Suresh Venkat
posible duplicado de las reducciones
Suresh Venkat

Respuestas:

7

Eche un vistazo a esta pregunta y especialmente a esta respuesta de Aaron Sterling. En resumen: "se conjetura que son nociones distintas".

Matías
fuente
Sé que si NP! = Co-NP, son nociones distintas porque la reducción de Turing los colapsa, pero ¿podría haber diferencias que no serían colapsos, por ejemplo, un problema en NPI bajo una reducción múltiple y en NPC bajo una reducción de Turing? ?
Ludovic Patey
@ Monoïd: NP ≠ coNP no implica (al menos de manera obvia) que las dos nociones de reducciones son distintas. Me temo que está confundiendo la clase NP (que se define independientemente de la elección de la noción de reducciones) con la clase de problemas de decisión reducibles a NP (que depende de la elección de la noción de reducciones).
Tsuyoshi Ito
Vaya, mi comentario anterior estaba equivocado. Si NP ≠ coNP, las dos nociones de reducciones son obviamente distintas (SAT es incondicionalmente Turing reducible a UNSAT, pero SAT es reducible a UNSAT si y solo si NP = coNP).
Tsuyoshi Ito
10

La "Jerarquía booleana" BP es una jerarquía completa de combinaciones de problemas NP bajo reducciones de Karp que están todas en P ^ NP.

Noam
fuente
9

Por lo que puedo decir, esta pregunta realmente comprende dos preguntas distintas, la primera de las cuales aparece en el título y la segunda se da después de la edición.

(1) ¿Las reducciones de muchos y las reducciones de Turing definen el mismo conjunto de problemas de NP completo (es decir, problemas que están tanto en NP como a qué SAT se puede reducir)? Si el NPC bajo las reducciones de Turing es el mismo que el NPC bajo las reducciones de muchos seguía siendo un problema abierto hace siete años, y no creo que se haya cerrado desde entonces. Vea esta encuesta de las noticias ACM SIGACT de junio de 2003 para más detalles.

(2) ¿Cuál es la clase de problemas a los que SAT tiene una reducción de Turing y viceversa? Esta es la clase de problemas NP-hard (bajo las reducciones de Turing) que se encuentran en P NP . Para obtener más información sobre esto, consulte la respuesta de Noam.

Peter Shor
fuente
El enlace no funciona.
T ....
8

Esto no responde a su pregunta, pero uno podría hacer la misma pregunta para reducciones más débiles. Por ejemplo, ¿cambia el conjunto de problemas NP-completos si permitimos solo reducciones de espacio logarítmico, o solo reducciones AC 0 , o incluso reducciones NC 0 . Un hecho sorprendente es que todos los problemas conocidos de NP completo están completos incluso con reducciones de NC 0 .

Referencia: Agrawal, M., Allender, E. y Rudich, S. 1997 Reducciones en la complejidad del circuito: un teorema de isomorfismo y un teorema de brecha.

Robin Kothari
fuente
¿Sigue abierta esta pregunta sobre reducciones más débiles? Si tengo un problema que era NP completo bajo las reducciones de P / poli o BPP, pero aparentemente no bajo las reducciones de P sin suponer suposiciones teóricas de números no comprobados, ¿vale la pena tomar nota?
Peter Shor el
@ Peter: en el artículo que he citado, se deja abierto si hay algún problema que sea NP completo bajo reducciones de tiempo polinomiales que no sea NP completo bajo reducciones AC ^ 0. Esta pregunta ha sido respondida reduciendo la complejidad de las reducciones . Muestran un problema que es NP-completo con reducciones ACC pero no reducciones AC ^ 0. Ninguno de estos documentos parece comentar sobre problemas que son NP-completos bajo reducciones más fuertes que el tiempo polinómico, y cómo eso se relaciona con la posibilidad de ser NP-completo bajo reducciones polytime.
Robin Kothari
1

Este artículo pretende mostrar que la existencia de un problema TF N EEXP que
[suficientemente difícil de resolver con cero error en el peor de los casos] implica la existencia de
"un lenguaje completo de Turing para NP que no es una tabla de verdad completa para NP. "

Por otro lado, no he intentado leer ninguna de sus pruebas reclamadas para ese resultado,
pero la Proposición 2 y / o su prueba demuestran una mala interpretación de la definición de ZPP :
Parece que realmente necesitan " FP puede resolver todo F ZPP ", en lugar de solo" ZPP = P ".


fuente