Bedeutet NP-Härte P-Härte?

22

Wenn ein Problem NP-hart ist (unter Verwendung von Polynomzeitreduzierungen), impliziert dies, dass es P-hart ist (unter Verwendung von Protokollraum- oder NC-Reduzierungen)? Es scheint intuitiv zu sein, dass, wenn es so schwierig ist wie ein Problem in NP, es genauso schwierig sein sollte wie ein Problem in P, aber ich verstehe nicht, wie man die Reduktionen verkettet und eine Reduktion des Protokollraums (oder der NC) erhält.

cc.complexity-theory np-hardness Adam Crume
quelle
4
Dies gilt, wenn Sie für beide Seiten die gleiche Art von Reduktionen verwenden, z. B. ist ein -Problem für die Reduzierung des Protokollspeicherplatzes auch Reduzierung des Protokollspeicherplatzes. P - h a r dNP−hardP−hard
Kaveh
Das heißt, Ihre Intuition ist korrekt, aber die Frage, die Sie gestellt haben, verlangt mehr als das (da Sie verschiedene Arten der Reduktion verwenden).
Kaveh
1
Der wichtigste Teil der Frage ist, welche Begriffe von Reduzierbarkeit Sie verwenden, aber diese Informationen werden irgendwie in Klammern gesetzt, als ob es sich um die am wenigsten wichtigen Informationen handelt!
Tsuyoshi Ito

Antworten:

31

Eine solche Implikation ist nicht bekannt. Insbesondere kann es sein, dass in welchem ​​Fall alle Probleme (einschließlich trivialer) unter Polyzeitreduktionen NP-hart sind (da die Reduktion nur das Problem lösen kann), aber triviale (insbesondere solche, die) liegen in L) sind unter logspace reductions sicher nicht P-hard (da sonst L = P). L≠P=NP

Das gleiche gilt für NC anstelle von L.

Noam
quelle
3
Vielen Dank für diese Antwort. Ich denke, für viele Leute - und zumindest für mich - schien diese Frage keine große Sache zu sein, aber nach dem Lesen Ihrer Antwort auf drei Sätze ist sie "offensichtlich" tief. (Auch danke für die Frage, @Adam Crume.)
Aaron Sterling