La dureté NP implique-t-elle la dureté P?

22

Si un problème est NP-difficile (en utilisant des réductions de temps polynomiales), cela signifie-t-il qu'il est P-difficile (en utilisant l'espace logarithmique ou les réductions NC)? Il semble intuitif que s'il est aussi difficile que n'importe quel problème dans NP, il devrait être aussi difficile que n'importe quel problème dans P, mais je ne vois pas comment enchaîner les réductions et obtenir une réduction de l'espace du journal (ou NC).

cc.complexity-theory np-hardness Adam Crume
la source
4
Cela est si vous utilisez le même genre de réductions pour les deux parties, par exemple , une problème des réductions log-space WRT est également P - h un r d réductions log-space WRT. NP-hunerréP-hunerré
Kaveh
c'est-à-dire que votre intuition est correcte mais la question que vous avez posée demande plus que cela (puisque vous utilisez différents types de réduction).
Kaveh
1
La partie la plus importante de la question est de savoir quelles notions de réductibilité vous utilisez, mais ces informations sont en quelque sorte mises entre parenthèses comme s'il s'agissait des informations les moins importantes!
Tsuyoshi Ito

Réponses:

31

Aucune implication de ce type n'est connue. En particulier, il se peut que L≠P=NP

Il en va de même pour NC au lieu de L.

Noam
la source
3
Merci beaucoup pour cette réponse. Je pense que pour beaucoup de gens - et du moins pour moi - cette question ne semblait pas très grave, mais après avoir lu votre réponse en trois phrases, elle est "évidemment" profonde. (Merci aussi pour la question, @Adam Crume.)
Aaron Sterling