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.
tutorsglobe.com hepatitis a assignment help-homework help by online hepatitis viruses tutors
Theory and lecture notes of Integration-Left, Right and Trapezoid Rules all along with the key concepts of functions and data, Left and Right endpoint rules, Trapezoid rule, Trapezoid rule for areas in the plane. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Integration-Left, Right and Trapezoid Rules.
The theory of strategic thinking along with the key concepts of strategy, coopetition, game theory, dominated strategy, nash equilibrium, network effect strategy, coopetition, game theory, dominated strategy, nash equilibrium, network effect and zero-sum game, get tutor's answer for managerial economics problems, homework help, assignment help.
tutorsglobe.com process of urea assignment help-homework help by online urea cycle tutors
Importance of Soil and Plant Tissue Analysis tutorial all along with the key concepts of Plant Tissue Analysis - Nutrient Concentration, Plant-Stalk Nitrate, Application of Plant Analysis, Application of Soil Analysis, Plant, Soil and Water Relationship, Soil Depth and Layering
www.tutorsglobe.com assignment help - systems have been classified in different ways, physical or abstract, open or closed, man-made information systems
www.tutorsglobe.com offers the hückel's rule homework help, the hückel's rule assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
tutorsglobe.com nineteenth century art assignment help-homework help by online humanities tutors
the sizes of wire are estimated through a device that is termed as gauges that contains plates of circular or oblong form comprising notches of dissimilar widths around their edges.
insulation tester (megger) applies dc (direct current) voltage to the insulation system and calculates the current that results.
Theory and lecture notes of Determining Internal Node Values all along with the key concepts of Variational Principles, finite element solution, Application to the steady state heat equation. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Determining Internal Node Values
tutorsglobe.com arrangement of flagella assignment help-homework help by online algae tutors
There is broad agreement that financial reporting standards have enhanced the quality of financial statements. However, we should be aware to the potential problems related with their use.
Linear Integrated Circuits tutorial all along with the key concepts of Digital ICs, Logic gates, Flip-flop, Calculator chip, Memory chip, Operational amplifiers, Advantages of Integrated Circuits, Classification, Monolithic Integrated Circuits, Hybrid or Multi-chip Integrated Circuits
Theory and lecture notes of Consumer Preference Theory all along with the key concepts of Assumptions about the consumer preferences, Cardinal vs. Ordinal Utility, Utility Surface, Diminishing MU, Properties of Indifference Curves. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Consumer Preference Theory.
1961194
Questions Asked
3689
Tutors
1487426
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!