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.
www.tutorsglobe.com offers business economics homework help, business economics assignment help, online business economics homework tutoring assistance, and writing assignments in business economics.
Other properties of group 14 tutorial all along with the key concepts of Chemical Properties of group 14, Carbides, Halides, Fluorocarbons, Hydrides, Oxides and Complex Formation
Theory and lecture notes of Lines in the Plane all along with the key concepts of Slope of a Line, Point-Slope Form of a Line, Slope-Intercept Form of a Line, General Form of a Line, Vertical and Horizontal Lines, Perpendicular Lines and Parallel Lines. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Lines in the Plane.
TutorsGlobe.com Organic Chemistry and classification of Organic Molecules Assignment Help-Homework Help by Online Access Chemistry Tutors
Fermi Surfaces tutorial all along with the key concepts of Brillouin zones, Effect of a crystal potential, Alkali metals, The noble metals, cubic divalent metals and Trivalent metals
www.tutorsglobe.com offers surface chemistry homework help, surface chemistry assignment help, online tutoring assistance, physical chemistry solutions by online qualified tutor’s help.
Basic Data Structures and their types-Assignment help and Homework help all along with the key concepts of Arrays, Vector Trick, Linked List, Variations of Linked List, Stack, stack applications and Queue
www.tutorsglobe.com offers Type of Standard homework help, assignment help, case study, writing homework help, online tutoring assistance by accounting tutors.
tutorsglobe.com structure of fungi assignment help-homework help by online fungi tutors
tutorsglobe.com social forestry assignment help-homework help by online forest resources tutors
Estimation and hypothesis testing Statistical Hypothesis, Null and Alternative Hypothesis, level of Confidence and Steps in Hypothesis Testing
Diagrams and charts show information in an easy and effective way. They available the information looks impressive and attractive.
tutorsglobe.com programming in assembly assignment help-homework help by online computer programming tutors
tutorsglobe.com example for demand function assignment help-homework help by online demand tutors
identification of the fault in a dvd player - firstly connect the dvd player along with tv receiver and switch on. there is no movement in the dvd player. it appears to be dead.
1950162
Questions Asked
3689
Tutors
1495183
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!