The problem that is in NP, but not in P

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.

Advertisements
This entry was posted in Complexity classes and tagged , , , , , . Bookmark the permalink.

3 Responses to The problem that is in NP, but not in P

  1. Joe Marshall says:

    I think you’re confused. Non-deterministic Turing machines are as computationally expressive as deterministic ones. There is nothing that one can compute that the other cannot.

  2. droope says:

    Holy shit! i didn’t understand anything at all!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s