Complexity: P & NP

Goals of this section: Given a model of computation and a measurement of complexity of computations, it is possible to state the inherent complexity of the class of problems. This is lower bound on the complexity of any algorithm which solves instances of given problem class. Model of computation considered are Turing machines, that is, the complexity measure is time as measured by number of transitions performed sequentially (other complexity measures, example: space). Understand the drastic difference among deterministic and non-deterministic computation, and concepts like P, NP, NP-complete, NP-hard. Satisfiability and other NP-complete troubles.

Decision problems and optimization problems: illustrations

Definition: Hamiltonian cycle in a graph G = (V, E): a cycle which comprises each of the vertices in V (exactly once)

Definition: The traveling salesman problem (TSP):

Weighted graph G = (V, E, w: E -> Reals), V = {1... n}, E = {(i, j) | i < j} (that is, often the complete graph Kn).

Weight (or length) of the path or cycle = sum of weights of its edges.

Given G= (V, E, w) find out a shortest Hamiltonian cycles, when any exist.

Definition: The clique in a graph G = (V, E): a subset V’ ⊆ V such that for each u, v ∈ V’, (u, v) ∈ E.

|V’| is the size of clique. The clique of size k is termed as a k-clique.

Definition: Clique troubles: Given G= (V, E), answer questions regarding the presence of cliques, determine maximum clique, enumerate all the cliques.

Illustration: The graph a) shown at left has precisely 1 Hamiltonian cycle, highlighted in b) The graph c) Has none. The complete graph K4 consists of 3 Hamiltonian cycles. d) The complete graph Kn has (n-1)! / 2 Hamiltonian cycles.

Illustration: Graph a) Consists of three maximum 3-cliques. The only cliques in graph c) are vertices and the edges, that is, 1-cliques and 2-cliques. Graph d) is the 4-clique, and every subset of its vertices is clique.

As the illustrations above show, ‘basically similar’ combinatorial problem frequently comes in distinct versions, some of which are optimization troubles, others decision troubles. The three problems: A) ‘Determine a maximum clique’, B) ‘What is the size of maximum clique’, C) ‘Is there a k-clique for a specified value k?’ clearly call for identical computational methods. Combinatorial problems in practice are generally concerned with optimization, that is, we search for an object that is best according to the given objective function. The complexity theory of this section, on other hand, is mostly concerned with the decision problem. To appreciate its practical relevance it is significant to understand that optimization troubles and decision problems are frequently related: any information regarding one kind of problem gives useful knowledge about the other. We differentiate 3 kinds of problems of seemingly rising difficulty:

Decision problems:

Given G, does G contain a Hamiltonian cycle? Given G and k, does G contain a k-clique?

Given G = (V, E, w) and a real number B, does G contain a Hamiltonian cycle of length ≤ B?

Determining the answer to a decision problem is frequently hard, while verifying a positive answer is frequently simple: we are shown an object and just have to confirm that it meets the specifications (example: trace the cycle shown in b).

Decision problems are naturally formalized in the terms of machines accepting languages, as follows: problem instances (example: graphs) are coded as strings and the code words of all examples which have the answer YES (example: Have a Hamiltonian cycle) form the language to be accepted.

Optimization problems:

Given G, build a maximum clique.

TSP: Given Kn = (V, E, w) find out a Hamiltonian cycle of the minimal total length.

Both the problems, of determining the answer and confirming it, are generally hard. When I claim to illustrate you a maximum clique, and it comprises k vertices, how do you confirm that I haven’t missed the bigger one? Do you have to catalog all the subsets of k+1 vertices to be sure that there is no (k+1)-clique? Nonetheless, confirming is generally simpler than finding a solution, as the claimed solution gives a bound which removes many sub-optimal candidates.

Enumeration problems:

Given G, build all Hamiltonian cycles or all cliques or all the maximum cliques.

Enumeration problems are resolved by the exhaustive search methods like backtrack. They are time consuming however frequently conceptually simple, apart from that when the objects should be enumerated in a prescribed order. The Enumeration is the method of last resort for resolving decision problems or optimization problems which admit no efficient algorithms, or for which no efficient algorithm is recognized. This is a costly method, as the number of objects to be examined frequently grows exponentially with the length of their explanation.

The complexity theory of this section is formulated in terms of decision problems, while in practice; most of the problems of interest are optimization problems!

In practice, barely any problem calls for a simple yes or no answer - nearly all the computations call for constructing a solution object of bigger complexity than a single bit! This is therefore significant to realize that the complexity theory of decision troubles can be made to apply optimization problems as well. The way to do this is to relate with an optimization problem an associated decision problem in such a way that the complexity of latter has implications for the complexity of former. We differentiate three

kinds of optimization troubles:

i) Optimization problem (that is, in strict sense): Determine an optimal solution.

ii) Computation problem: Find out the value of optimal solution.

iii) Bound problem: Given a bound B, find out whether the value of optimal solution is above or beneath B.

Intuitively, a solution to problem i) provides more information than ii), that in turn includes more information than iii) Certainly, for all ‘reasonable problems’, an effective solution to an optimization problem in the strict sense:

i) Implies an effective solution to the corresponding valuation problem ii) By simply evaluating the cost of this solution. Obviously, one can build pathological illustrations where the computation function is much complex, or even non-computable. In that condition, given a solution s, we may not be capable to evaluate its value v(s). However such cases do not seem to take place in practice.

In turn, an effective solution to an evaluation problem a) implies an effective solution to the corresponding bound problem b) - just by comparing the two numbers.

The opposite direction is less apparent. Nonetheless, we show that the solution to bound problem i) Helps in determining a solution to the computation problem ii) That in turn helps in determining a solution to the optimization problem iii) There is a considerable cost included, however this cost is ‘polynomial’, and in generous complexity measure of this section we avoid polynomial costs. However iv) comprises less information than ii) and ii) generally less than i), it is not surprising that even a small quantity of information can be exploited to speed up the solution to harder problem, as follows.

To exploit iii) in solving ii), we employ the fact that the possible values of the combinatorial problem are as a rule discrete and can be taken to integers. Suppose we can resolve the bound problem iii) in time T. For the corresponding computation problem ii) one generally knows a priori that the value lies in a certain range [L, U] of integers. Employing binary search, we resolve the evaluation problem with log | U - L | calls to bound problem iii) and thus in time T log | U - L |.

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.