Czy twardość NP oznacza twardość P?

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

Dotyczy to w przypadku korzystania z tego samego rodzaju ulg dla obu stron, na przykład

problemem WRT redukcji log-przestrzeń jest również

redukcje wrt log-space.

N P - h a r d

$\mathbf{NP-hard}$

P - h a r d

$\mathbf{P-hard}$

— 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

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,

Ż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 \ne P = NP$

To samo dotyczy NC zamiast L.

— Noam
źródło

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