The class P of problems solvable in polynomial time:

Practically all the standard combinatorial algorithms represented in a course on Algorithms and Data Structures run in the polynomial time. They are sequential algorithms which terminate after a number of computational steps which is bounded by some polynomial p(n) in size n of input data, as measured by the number of data items which define the problem. The computational step is any operation which takes constant time, that is, time independent of n.

In practical algorithm analysis there is a pretty amount of leeway in the definition of ‘computational step’ and ‘data item’. For illustration, an integer might be considered a single data item, in spite of of its magnitude, and any arithmetic operation on integers as the single step. This is rational if we know a priori that all numbers produced are bounded by some integer ‘maxint’, and is unreasonable for the computations which produce numbers of unbounded magnitude.

When complexity theory based on the Turing machines definition is clear: the computational step is a transition performed, a data item is the character of alphabet, read or written on the square of tape. The alphabet is generally selected to be {0, 1} and the size of data is measured in bits. Whenever studying the class P of problems solvable in the polynomial time, we just consider deterministic TMs which halt on all inputs.

Let tM: A* -> Integers be the number of steps performed by M on input x ∈ A*.

This section deals with TMs whose running time is bounded by certain polynomial in the length of input.

Definition: TM M is or runs in polynomial time if and only if ∃ polynomial p such ∀x ∈ A*:  tM ( x ) ≤ p( |x| )

Definition: P = {L ⊆ A* | ∃ TM M, ∃ polynomial p in such a way that L = L(M) and ∀x ∈ A*: tM ( x ) ≤ p( |x|)}

Note that we do not specify the accurate version of TM to be employed, in specific the number of tapes of M is left open. This might be surprising in view of the fact that the multi-tape TM is much quicker than the single-tape TM.

The detailed analysis exhibits that ‘much faster’ is polynomial bounded: The single-tape TM S can simulate any multi-tape TM M with utmost a polynomial slow-down: for any multi-tape TM M there is a single-tape TM S and the polynomial p such that for each x ∈ A*, tS (x ) ≤  p( tM (x)). This simulation property and the fact which a polynomial of a polynomial is again a polynomial, makes the definition of class P very robust.

The question occurs whether the generous accounting which avoids polynomial speed-ups or slow-downs is of practical relevance. After all, such are much bigger differences than avoiding constant factors as one does routinely in asymptotic. The answer is definite YES, based on some considerations:

A) Practical computing employs random access memory, not sequential storage like tapes. Therefore, the issue of how many tapes are employed doesn’t even occur. The theory is formulated in terms of TMs, instead of more realistic models of computation like conventional programming languages, for the sake of mathematical accuracy. And it turns out that slowness of tape manipulation gets absorbed, in comparison with the RAM model, by the polynomial transformations we avoid so generously.

B) Most practical algorithms are of the low degree, like O(n), O(n log n), O(n2), or O(n3). Low-degree polynomials rise slowly adequate that the corresponding algorithms are computationally feasible for most values of n which take place in practice. Example: for n = 1000, n3 = 109 is a number of moderate size whenever compared to processor clock rates of 1 GHz and memories of 1 GByte. The polynomial growth rates are very slow as compared to exponential growth (consider 21000).

C) This complexity theory, similar to any theory at all, is a model which mirrors some aspects of reality well and others badly. This is the responsibility of programmer or algorithm designer to find out in each particular case, whether or not an algorithm “in P” is practical or not.

Illustrations of problems (perhaps?) in P:

A) Each and every context-free language is in P. We know O(n3) parsing algorithm which solves the word problem for CFLs, Here n is the length of input string.

B) The complexity of problems which include integers based on the representation. Luckily, with the usual radix representation, the selection of radix r > 1 is immaterial (why?). However when we select an exotic notation, everything might modify. For illustration, when integers were given as a list of their prime factors, most of the arithmetic problems would become simpler. Paradoxically, when integers were given in unwieldy unary notation, some things may as well become simpler according to the measure of this section. This is as the length of the unary representation <k>1 of k is exponential in length of radix r≥2 representation <k> r. Given an exponentially bigger input, a polynomial-time TM is permitted to use an exponentially bigger computation time as compared to the ‘same’ problem given in the form of concise input.

The given illustration describes the fact that the complexity of arithmetic problems based on the number representation selected. The supposed difficulty of factoring an integer lies at the core of the modern cryptography.

Factoring algorithms known nowadays need, in worst case, time exponential in the length that is, number of bits, of the radix representation of number to be factored. However there is no proof that factoring is NP-hard-according to today’s knowledge, there may exist polynomial-time factoring algorithms. This possibility gained the plausibility whenever it was proven that primarily, that is, the problem of finding out whether a natural number (symbolized in radix notation) is prime or composite, is in P.

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.