http://i.imgur.com/QUlm1W2.jpg
不好意思想请问一下11题的(3)是错在哪边？
题目右下角是我尝试照着题意画的转换图
感觉起来是B之instance花O(nlgn)转换到A问题，然后花O(T(n))解A的instance，就等价于B之decision
所以看起来应该是B<=(A比较难)
所以错的地方应该是lower bound of A=Ω(n2 )
这段改成upper bound of A=O(n2 )是不是就对了？

lower bound 要在简单的问题上

所以lower bound是要在B上吗？