¿La dureza NP implica dureza P?

22

Si un problema es NP-hard (usando reducciones de tiempo polinomiales), ¿eso implica que es P-hard (usando espacio de registro o reducciones NC)? Parece intuitivo que si es tan difícil como cualquier problema en NP, debería ser tan difícil como cualquier problema en P, pero no veo cómo encadenar las reducciones y obtener una reducción de espacio de registro (o NC).

cc.complexity-theory np-hardness Adam Crume
fuente
44
Esto es válido si usa el mismo tipo de reducciones para ambos lados, por ejemplo, un problema de wrt log-space reductions también es wrt log-space reductions. P - h a r dNP−hardP−hard
Kaveh
es decir, su intuición es correcta, pero la pregunta que ha formulado pide más que eso (ya que está utilizando diferentes tipos de reducción).
Kaveh
1
La parte más importante de la pregunta es qué nociones de reducibilidad utilizas, ¡pero esta información se pone entre paréntesis como si fuera la información menos importante!
Tsuyoshi Ito

Respuestas:

31

No se conoce tal implicación. En particular, puede ser que en cuyo caso todos los problemas (incluidos los triviales) son NP-hard bajo reducciones de poli-tiempo (ya que la reducción solo puede resolver el problema), pero triviales (en particular los que mentir en L) seguramente no son P-hard bajo las reducciones de espacio de registro (como lo contrario L = P). L≠P=NP

Lo mismo ocurre con NC en lugar de L.

Noam
fuente
3
Muchas gracias por esta respuesta. Creo que para mucha gente, y al menos para mí, esta pregunta no parecía ser un gran problema, pero después de leer la respuesta de tres oraciones, es "obviamente" profunda. (También, gracias por la pregunta, @ Adam Crume.)
Aaron Sterling