演算法問題請教(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 statement is true

d. all of the above

應該可以推論出

L1<=L2

所以b是錯的

但是要如何得知答案是a還是c?

感激不盡

2 個解答

評分
  • 7 年前
    最佳解答

    The answer is (c).

    (a) is wrong because we still do not know if NP != p is true or false.

    (a) can only be chosen if NP != p

    (b) can only be chosen if NP = p

    (c) is right for the reason that a problem must be in NP in order to be polynomial-reducible to another NP.

    2013-02-19 22:20:19 補充:

    Sorry that I did not see your follow-up question here:

    Before starting the argument, let's see how P, BPP, and NP are related.

    1. P is a subset of BPP and BPP is a subset of NP

    2. if NP = P, then P = BPP = NP

    2013-02-19 22:23:47 補充:

    if NP != P, then

    for (1), L2 is in P => L1 is also in P and because P is a subset of BPP,

    L1 is in P => L1 is in BPP

    for (2) L2 is in BPP => L1 is also in BPP and because BPP is a subset of NP

    L1 is in BPP => L1 is in NP

    2013-02-19 22:24:37 補充:

    if NP = P, then NP = BPP = P, so both (1) and (2) must be true.

    2013-02-19 22:25:17 補充:

    So, both 1 and 2 are true in both cases when NP = P and NP != P.

  • 7 年前

    您好, 我想再請教一下, 釐清一下我的觀念

    1) if L1 is polynomial-time reducible to L2, and L2 is in P, then L1 is in BPP;

    2) if L1 is polynomial-time reducible to L2, and L2 is in BPP, then L1 is in NP.

    這樣的話無論是1)跟2)都是 不確定 對嗎?

    謝謝您

還有問題?馬上發問,尋求解答。