First of all, we’re going to create a string by asking this question: A NDTM, trying to solve an undecidable problem, will run k steps? Making a trivial simulation, the machine will run k steps. The answer to the problem is yes.
Second, we’ll take a part of the string generated by the machine (let’s say that the whole string is ‹MND› and the fragment is ‹MND‘›) and ask this question to a DTM: Is this string ‹MND‘›, generated by a NDTM?
About this problem we can say:
– The problem is not only undecidable, is unsolvable… for obvious reasons (like, running until the end of time, a DTM will not find the algorithm which generated the string because is a non-deterministic algorithm). So, it cannot be solved, not only in polynomial time, but it cannot be solved at all. That is: the problem is not in P.
– The same problem can be solved by a NDTM, in polynomial time, because there is a non-deterministic algorithm which will write ‹MND› just by choosing, every time it writes down, the right symbol of the answer. At the same time, giving to a DTM the string ‹MND‘› and the string ‹MND› itself, it can easily (meaning in polynomial time) verify that ‹MND‘› is a part of ‹MND›. That is: the problem is in NP.
Third, this being a problem in NP but not in P, we’ll say that P is not equal to NP, and we’ll say that P is a strict subset of NP.
For the beauty of it all, I’ll reformulate the problem: Is ‹this› random? With the (flawed) note: a string generated by a NDTM trying to solve an undecidable problem is true randomness.