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

### 2 個解答

• 最佳解答

(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.

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

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)都是 不確定 對嗎?

謝謝您