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.
Get the optimum E-Business Assignment Help service from top experts at low prices and excel your academic grades!
www.tutorsglobe.com offers substitution of the hydroxyl group homework help, assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
tutorsglobe.com microtomy and hand sectioning assignment help-homework help by online biological techniques tutors
tutorsglobe.com clinical findings assignment help-homework help by online characteristics of trematoda tutors
Bogged down with academic tasks? Avail top-rated Thermal Physics Assignment Help service to score well at low prices.
solanaceae involves about 90 genera and in excess of 2,800 species. the plants are extensively distributed in tropical and subtropical regions.
Theory and lecture notes of Structure of Data management system all along with the key concepts of structure of data management system, Dictionary, Data Base manager, Data Communications, Transaction Management. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Structure of Data management system.
tutorsglobe.com indifference curve assignment help-homework help by online indifference curve approach tutors
The value added statement (VAS) came into existence in the middle 1970s following publication of an influential discussion document that entitled The Corporate Report. The Corporate Report argued for the inclusion of the VAS under the annual report.
tutorsglobe.com structure of antibodies assignment help-homework help by online structure and characteristics of antibodies tutors
Molar Heat Capacities of Gases tutorial all along with the key concepts of Molar Heat Capacities of Gases, Work Done by the Expanding Gas, Molar Heat Capacities at Constant Volume and Constant Pressure, Isothermal and Adiabatic Expansion of Gases
tutorsglobe.com translocation of solutes assignment help-homework help by online mineral nutrition tutors
There is a unique adjustment for every channel. Resonance is acquired with coil’s distributed capacitance, stray and trimmer capacitors. The oscillator coil is generally constructed with an aluminium or brass screw as the core for fine tuning.
tutorsglobe.com economic importance of gymnosperms assignment help-homework help by online spermatophytes tutors
looking for instant and first class set theory assignment help service? hire phd experts and get authentic papers with 24x7 support to score a++.
1950174
Questions Asked
3689
Tutors
1479798
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!