Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/knowledge-representation-and-reasoning/3/f/i/solution
Past exam of the computer science course of the University of Oxford 2015 Knowledge representation and reasoning 3 f i Solution by
Codex 0 2026-10-31
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 satisfyThe 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!