Dureza NP implica dureza P?

22

Se um problema for difícil para NP (usando reduções de tempo polinomiais), isso implica que é difícil para P (usando espaço de log ou reduções de NC)? Parece intuitivo que, se é tão difícil quanto qualquer problema em NP, deve ser tão difícil quanto qualquer problema em P, mas não vejo como encadear as reduções e obter uma redução no espaço de log (ou NC).

cc.complexity-theory np-hardness Adam Crume
fonte
4
Isto é válido se utilizar o mesmo tipo de redução para ambos os lados, por exemplo, um problema wrt reduções de log-espaço é também P - h uma r d reduções de log-wrt espaço. NP−hardP−hard
Kaveh
ou seja, sua intuição está correta, mas a pergunta que você pediu exige mais do que isso (já que você está usando diferentes tipos de redução).
Kaveh
1
A parte mais importante da pergunta é quais noções de redutibilidade você usa, mas essas informações são colocadas entre parênteses como se fossem as informações menos importantes!
Tsuyoshi Ito

Respostas:

31

Nenhuma implicação desse tipo é conhecida. Em particular, pode ser que nesse caso, todos os problemas (incluindo os triviais) são NP-duros sob reduções de tempo poli (como a redução pode apenas resolver o problema), mas triviais (em particular aqueles que em L) certamente não são P-hard sob reduções de espaço de log (caso contrário, L = P). L≠P=NP

O mesmo vale para NC em vez de L.

Noam
fonte
3
Muito obrigado por esta resposta. Penso que para muitas pessoas - e pelo menos para mim - essa pergunta não parecia grande coisa, mas depois de ler sua resposta de três frases, ela é "obviamente" profunda. (Também, obrigado pela pergunta, @ Adam Crume.)
Aaron Sterling