演算法問題請教(Complexity theory)

Let L1, L2 be languages and let X,Y be either P or NP. Consider the statement: if L1 is polynomial-time reducible to L2, and L2 is in X, then L1 is in Y. Which of the following holds: a.When X=P and Y=P, then the statement is true b.When X=P and Y=NP, then the statement is true c.When X=NP and Y=NP, then the... 顯示更多 Let L1, L2 be languages and let X,Y be either P or NP.
Consider the statement: if L1 is polynomial-time reducible to L2,
and L2 is in X, then L1 is in Y. Which of the following holds:

a.When X=P and Y=P, then the statement is true
b.When X=P and Y=NP, then the statement is true
c.When X=NP and Y=NP, then the statement is true
d. all of the above

應該可以推論出
L1<=L2
所以b是錯的
但是要如何得知答案是a還是c?

感激不盡
2 個解答 2