--%>
Assignment Help - homework help

  Problem reduction and classes of equivalent problems, Complexity P & NP

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.

761_convex hull.jpg

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.

92_sorting algorithm.jpg

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.

26_sorting algorithm_1.jpg

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.