Yahoo Answers: Answers and Comments for 演算法問題請教(Complexity theory) [程式設計]
Copyright © Yahoo! Inc. All rights reserved.
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
From Jelerak
zhHantTW
Mon, 11 Feb 2013 04:33:43 +0000
3
Yahoo Answers: Answers and Comments for 演算法問題請教(Complexity theory) [程式設計]
292
38
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
https://s.yimg.com/zz/combo?images/emaillogotw.png

From Jelerak: 您好, 我想再請教一下, 釐清一下我的觀念
1) if L1 is polynomialt...
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
Mon, 11 Feb 2013 23:49:30 +0000
您好, 我想再請教一下, 釐清一下我的觀念
1) if L1 is polynomialtime reducible to L2, and L2 is in P, then L1 is in BPP;
2) if L1 is polynomialtime reducible to L2, and L2 is in BPP, then L1 is in NP.
這樣的話無論是1)跟2)都是 不確定 對嗎?
謝謝您

From prisoner26535: The answer is (c).
(a) is wrong because we st...
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
https://tw.answers.yahoo.com/question/index?qid=20130211000016KK00758
Mon, 11 Feb 2013 14:33:55 +0000
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 polynomialreducible to another NP.
20130219 22:20:19 補充：
Sorry that I did not see your followup 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
20130219 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
20130219 22:24:37 補充：
if NP = P, then NP = BPP = P, so both (1) and (2) must be true.
20130219 22:25:17 補充：
So, both 1 and 2 are true in both cases when NP = P and NP != P.