Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/knowledge-representation-and-reasoning/3/f/i/solution

For polynomial-time many-one reductions, an unconditional example is the empty language:
A procedure that rejects every input decides it in constant time, so it belongs to P and hence NP. It is not NP-hard: the nonempty formal language belongs to NP, but no many-one reduction can satisfy
The right-hand side is always false. Thus the hardness condition fails without assuming . Giving an ordinary nontrivial problem in P would not establish the requested separation unconditionally, because that would require excluding the possibility .

New to topics? Read the docs here!