一道算法题
请问A后面的多项式是什么意思？这道证明题该如何解决呢？
[解决办法]
We claim that if P=NP, then anything in P (except full language and empty language) is NP-complete.
Suppose a language L is in P. Let X be in L and Y be not in L. We try to reduce 3-SAT to L by the following reduction: directly solve 3-SAT in polynomial time, and then map the input to X if the 3-SAT is true, and to Y if the 3-SAT is false. It is a polynomial time reduction, so L is also NP-complete.
In this problem, clearly A is in P (A is even a regular language), and not full not empty. By above argument, A is NP-complete.
