Problem reduction and classes of equivalent problems:
The scientific advances frequently follow from the successful attempt to establish similarities and relationships among seemingly various problems. In mathematics, these relationships are formalized in two manners:
a) Problem A can be reduced to the problem B, A ≤ B, implies that when we can solve B, we can as well solve A
b) Problems A and B are equal, A ≤ B and B ≤ A, implies that when we can solve either problem, we can as well solve the other, generally with an equivalent investment of resources. While here we use “≤” in an intuitive sense, definition of polynomial reducibility, represented by “≤p”.
This section is all about reducing certain problems to others, and to characterizing various prominent classes of equivalent problems. Consider some illustrations.
Sorting as the key data management operation. Answering nearly any query regarding an unstructured set D of data items needs, at least, looking at each data item. When the set D is organized according to certain helpful structure, on other hand, many significant operations can be done more rapidly than in linear time. Sorting D according to some helpful total order, for illustration, enables binary search to determine, in logarithmic time, any query item given by its key. Since a data management operation of main significance, sorting has been studied extensively. In RAM model of computation, the worst case complexity of sorting is Θ(n log n). This fact can be employed in two ways to bind the complexity of many other troubles:
A) To show that some other trouble P can be resolved in time O(n log n), as P reduces to sorting, and
B) To show that some other trouble Q needs time Ω(n log n), as sorting reduces to the Q. Two illustrations:
i) Determining the median of n numbers x1, .., xn can be completed in time O(n log n). After sorting x1, .., xn in an array, we determine the median in constant time as x [n div 2]. The more sophisticated analysis exhibits that the median can be found out in linear time, however this doesn’t detract from the fact that we can rapidly and simply establish an upper bound of O(n log n).
ii) Determining the convex hull of n points in plane needs time Ω(n log n). The algorithm for computing the convex hull of n points in plane takes as input a set {(x1, y1), .. , (xn, yn)} of coordinates and delivers as output a sequence [(xi1, yi1), .. , (xik, yik)] of extremal points, that is, those on convex hull, ordered clock-wise or counter-clockwise. The figure below exhibits 5 unordered input points and ordered convex hull.
We now decrease the sorting problem of known complexity Ω(n log n) to convex hull problem as shown in next figure. Given a set {x1, .. , xn} of reals, we produce the set {(xi, xi2), .. , (xn, yn2)} of point coordinates. Due to convexity of function x2, all points lie on the convex hull. Therefore a convex hull algorithm returns the sequence of points ordered by rising x-coordinates. After dropping irrelevant y-coordinates, we get the sorted sequence [x1, .. , xn]. Therefore, a convex hull algorithm can be employed to get a ridiculously complicated sorting algorithm, however that is not our goal. The main aim is to show that the convex hull problem is at least as complicated as sorting - if it was significantly simpler, then sorting would be simpler, too.
The given figure describes problem reduction in common. Given a problem U of unknown complexity and a problem and algorithm K of the known complexity. The coding function c converts a given input I for one trouble to input I* for the other, and the decoding function d converts output O* to output O. This kind of problem reduction is of interest only if the complexity of c and of d is no bigger than the complexity of K, and if the input transformation I* = c(I) leaves the size n = | I | of the input data asymptotically unmodified: | I*| ∈ Θ ( n).| This is what we suppose in the following.
Deriving the upper bound. At left we build a solution to the problem U of the unknown complexity by detour U(I) = d( K(c(I))). Letting |c|, |K| and |d| signifies for the time needed for c, K and d, correspondingly, this detour confirms the upper bound |U| ≤ |c| + |K| + |d| . Beneath the usual supposition that |c| ≤ |K| and |d| ≤ |K|, this bound asymptotically decreases to |U| ≤ |K|. More explicitly: When we know that K(n), c(n), d(n) are all in O( f(n)), then as well U(n) ∈ O( f(n)).
Deriving the lower bound. At right we argue that the problem U of unknown complexity |U| is asymptotically at least as complicated as a problem K for which we know the lower bound, K(n) ∈ Ω( f(n)). Counter-intuitively, we decrease the known problem K to unknown problem U, obtaining the inequality |K| ≤ |c| + |U| + |d| and |U| ≥ |K| - |c | - |d|. When K(n) ∈ Ω( f(n)) and c and d are strictly less complex than K, that is, c(n) ∈ o(f(n)), d(n) ∈ o( f(n)), then we get the lower bound U(n) ∈ Ω( f(n)).
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 antibodies assignment help-homework help by online immunology tutors
tutorsglobe.com mechanism of muscle contraction assignment help-homework help by online muscles tutors
tutorsglobe.com parasitic plants assignment help-homework help by online mode of nutrition tutors
TutorsGlobe.com Mole Concept-II Assignment Help-Homework Help by Online Access Chemistry Tutors
tutorsglobe.com co-ordination systems assignment help-homework help by online human physiology tutors
Four-Vector Formulation of Electrodynamics tutorial all along with the key concepts of Transformation Properties of the Differential Operator, Four-vector Form of Continuity Equation, Four-vector Form of Maxwell's Equations, Transformation of Fields
tutorsglobe.com basic techniques of plant tissue culture assignment help-homework help by online plant tissue culture tutors
tutorsglobe.com samuelsons definition assignment help-homework help by online nature and scope of economics tutors
Life Cycles of Seed Plants tutorial all along with the key concepts ofStages in the Life-cycle of Flowering Plants, Seed Stage, Germination, Growth, Reproduction, Pollination, Spreading Seeds
the claims are generally categorized into - equity (owner’s claim) and liabilities (claims of outsiders). further the liabilities are classified as either current or non-current.
hydrogen bonding tutorial all along with the key concepts of intermolecular hydrogen bonding, intramolecular hydrogen bonding, effects of hydrogen bonding, boiling point and melting point, water solubility, polarising power
tutorsglobe.com digestion assignment help-homework help by online biochemistry tutors
identification of the fault given in a tv receiver - very the tv receiver is switched on firstly. the image on the screen with no colour. adjust the colour control. there is on the screen no colour picture.
Theory of Sampling tutorial all along with the key concepts of Fundamental principles of sampling, Sampling techniques, Types of Samples, Gross and Laboratory size Samples, Chain of custody procedure, Treatment or Preparation of Sample, Statistics of Sampling, Sample Decomposition
tutorsglobe.com average variable cost assignment help-homework help by online short run average cost curves tutors
1940047
Questions Asked
3689
Tutors
1453766
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!