Czy twardość NP oznacza twardość P?

22

Jeśli problem jest trudny dla NP (przy użyciu wielomianowych redukcji czasu), czy to oznacza, że ​​jest trudny dla P (przy użyciu przestrzeni dziennika lub redukcji NC)? Wydaje się intuicyjne, że jeśli jest tak trudny jak jakikolwiek problem w NP, powinien być tak trudny jak jakikolwiek problem w P, ale nie widzę, jak połączyć łańcuchowe redukcje i uzyskać redukcję przestrzeni logów (lub NC).

cc.complexity-theory np-hardness Adam Crume
źródło
4
Dotyczy to w przypadku korzystania z tego samego rodzaju ulg dla obu stron, na przykład problemem WRT redukcji log-przestrzeń jest również P - h r d redukcje wrt log-space. N.P.-hzarreP.-hzarre
Kaveh
tzn. twoja intuicja jest prawidłowa, ale pytanie, które zadałeś, wymaga więcej niż tylko tego (ponieważ używasz różnych rodzajów redukcji).
Kaveh
1
Najważniejszą częścią pytania jest to, jakie pojęcia redukowalności stosujesz, ale ta informacja jest w jakiś sposób umieszczona w nawiasach, tak jakby była to najmniej ważna informacja!
Tsuyoshi Ito,

Odpowiedzi:

31

Żadna taka implikacja nie jest znana. W szczególności może się zdarzyć, że w którym to przypadku wszystkie problemy (w tym trywialne) są NP-trudne przy zmniejszeniu wielomianu (ponieważ redukcja może po prostu rozwiązać problem), ale trywialne (w szczególności te, które leżą w L) z pewnością nie są twarde w P przy zmniejszeniu przestrzeni logów (w przeciwnym razie L = P). L.≠P.=N.P.

To samo dotyczy NC zamiast L.

Noam
źródło
3
Dziękuję bardzo za tę odpowiedź. Myślę, że dla wielu ludzi - a przynajmniej dla mnie - pytanie to wydawało się niczym wielkim, ale po przeczytaniu odpowiedzi na trzy zdania jest „oczywiście” głębokie. (Również dzięki za pytanie, @Adam Crume.)
Aaron Sterling