Assignment Help - homework help

  The class NP of problems solvable in non-deterministic polynomial time, Complexity P & NP

The class NP of problems solvable in non-deterministic polynomial time:

‘NP’ stands for ‘non-deterministic polynomial’. This is instructive to introduce two distinct however equivalent definitions of NP, as each definition highlights a distinct key aspect of NP. The original definition explicitly introduces the non-deterministic TMs:

Definition: NP = {L ⊆ A*| ∃ NTM N, ∃ polynomial p in such a way that L = L(N) and ∀x ∈ A*: tN (x) ≤ p( |x|)}

Note that this varies from the definition of P merely in the single letter ‘N’ in the phrase “∃ NTM N ..”, pointing out that we signify non-deterministic Turing machines. We had observed that deterministic and non-deterministic TMs are uniformly powerful in the existence of unbounded resources of time and memory. However there is a big difference in terms of time they take for some computations. The NTM pursues concurrently a number of computation paths which can grow exponentially with the length of computation.

Since of many computation paths pursued concurrently we should redefine the function tN: A* -> Integers which measures the number of steps performed. An input x ∈ A* might be accepted all along a short path and also all along a long path, and some other paths might not terminate. Thus we define tN(x) as the minimum number of steps executed all along any accepting path for x.

While the original definition of NP in terms of the non-deterministic TMs consists of the intuitive interpretation through parallel computation, an equivalent definition mainly based on deterministic TMs is possibly technically simpler to handle. The fact that such two definitions are equivalent gives two different manners of looking at NP.

The motivation for second definition of NP comes from the observation that it might be hard to decide whether a string meeting certain specifications exists; however that it is frequently simpler to decide whether or not a given string meets the specifications. In another words, determining a solution, or merely finding out whether a solution exists, is harder than checking a proposed solution’s accuracy. The fact that this intuitive argument leads to the rigorous definition of NP is surprising and helpful!

In the given definition, the language L explains a problem class, example: all graphs with a desired property; the string w explains a problem instance, example: a specific graph G; the string c = c(w), termed as a ‘certificate for w’ or a witness, plays the role of a key which ‘unlocks w’: the pair w, c is simpler to check than w alone!

Definition: NP is a class of languages which have deterministic polynomial-time verifiers.

Definitions Df1 and Df2 give two distinct interpretations of similar class NP: Df1 in terms of parallel computation and Df2 in terms of sequential verification. The technical benefit of Df2 is that the theory of NP can be developed by using only deterministic TMs that are simpler than NTMs. We now present an intuitive argument that the two definitions are equal.

Df1 -> Df2 (‘simulate and check’): When L is in NP according to Df1, there is a NDTM N with the given property: every w ∈ L consists of an accepting path p of length polynomial in |w|. This is tempting to merely eliminate the transitions of N which are not executed all along the path p, however this doesn’t turn N to a deterministic TM, as different w’s might use various transitions. Rather, we construct a DTM M which reads as input a string <w, N, P> which denotes the following information: the word w to be accepted, the NTM N, the accepting path p. M is a universal TM which interprets the explanation of N: at all step all along the path p, M checks that this step is one of the probable transitions of N on input w. In this construction, the pair <N, p> is w’s certificate.
Df2 -> Df1 (‘guess and check’): We present the idea by using an illustration the problem of Hamiltonian cycle.

According to Df2, there is a DTM M which confirms <G, c> in polynomial time, where the certificate c is the Hamiltonian cycle of G. Build a NTM N which first produces in parallel lists of n numbers v1, v2, .., vn,  vi ∈ 1 .. n. Each vi can be produced one bit at a time in logarithmic time, the whole list in time n log n. All lists are checked for the syntactic accuracy in the sense that there are no repetitions of the vertex numbers, and that any two consecutive vertices, comprising vn v1, are the edges of G. This checking is similar to the verification completed by the deterministic TM M, however the non-deterministic N does it on all lists concurrently. When anyone list is confirmed as being a Hamiltonian cycle, then N accepts <G>.

From both the definitions Df1 and Df2 it is obvious that P ⊆ NP. From Df1 since a DTM is a special case of a NTM. From Df2 since P is the class of languages L which need no certificate, therefore we can take the null string as a trivial certificate for all the words of L.
P = NP? Is one of the outstanding questions of theory of computations, so far unanswered? All experience and intuition recommends that P ≠ NP. Non-determinism gives computing power which grows exponentially with the length of sequential computation. In time that a DTM executes t steps, a NTM can execute at least 2t steps. While a DTM should backtrack to explore alternatives, the NTM explores all the alternatives at similar time. The belief that P ≠ NP is too strong that nowadays many researchers prove theorems that end with the caveat “..unless P = NP”. By this they signify to imply that the theorem is to be considered empirically true, that is, as true as the conjecture P ≠ NP.  However mathematics has its own severe rules as to what comprises a theorem and a proof, and nowadays there is no proof in sight to provide the conjecture P ≠ NP the status of theorem.

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
Home | Company Overview | Services | Discover Q&A | Sitemap | Contact Us | T & C | Refund Policy | Copyright Policy | Blog | Q&A | Directory

©TutorsGlobe All rights reserved 2022-2023.