Complexity

Time Complexity



Subjects to be Learned

Contents

In the previous sections we have learned that some problems are unsolvable by Turing machines hence by computers. No one can write computer programs that solve those problems and halt after a finite amount of time. A problem is solvable if some Turing machine can solve it in finite time. Even if it takes a million years to solve a problem, it is still solvable. However, in practice if it takes a million years, it is as good (or bad) as unsolvable. For many problems a day or even an hour would be too long. In this section we are going to study solvable problems and learn a hierarchy of solvable problems based on the computation time required to solve them. The measure for computation time we use is the worst case time. It is estimated by counting the largest possible number of key operations to be performed in terms of the input size. For more detailed review of this, O(f(x)) (big-oh) and other related subjects click here.

Among the solvable problems there are problems that can be solved by algorithms with the worst case time which is a polynomial in the problem size (polynomial time algorithms). For example a binary search takes O(lg n) time, a quick sort needs O(n2) time, a heap sort needs O(n lg n) time. They are all polynomial time algorithms. There are also problems that must be solved at best by exponential time algorithms in the worst case. For example, as we are going to see below, the satisfiability problem for the propositional dynamic logic is proven to take exponential time to solve in the worst case. They take much more time to execute than polynomial time algorithms. Then there are problems that require double exponential ( e.g. 22n ) time algorithms, problems that need k-exponential time algorithms, where k is a natural number, etc. and there are problems that require algorithms with the worst case time worse than k-exponential time for any natural number k. The problems that can not be solved with any polynomial time algorithm are called intractable problems .

Let us see some of those intractable problems. In logic there is a well known problem of "satisfiability". This is the problem of asking whether or not a given formula can take the value true for some values of its variables. For example the formula ( P V ~P ) is always true, where P is a propositional variable. So it is certainly satisfiable. Similarly ( P V Q ) is also satisfiable. But (P ^ ~P ) is always false. So it is not satisfiable. One can ask the same question for formulas of first order predicate logic, second order logic, etc.
Before proceeding to predicate logic let us consider the following logic called propositional dynamic logic (PDL for short). This is a propositional logic with an extra construct (proposition) after(A, S), where A is an algorithm and S is a statement. after(A, S) says that S is true after executing A. For example "after( if P then Q else ~Q, ~Q )" and "if P then after( if P then Q else ~Q, Q )" , where P and Q are propositions, are propositions of PDL. They are both satisfiable.
The satisfiability problem for PDL is known to take at least exponential time to solve in the worst case.

The satisfiability problem becomes even harder when logic becomes more complex. For example the satisfiability problem for Presburger arithmetic is double-exponential (2-fold exponentail), that is it requires at least O( aan ) time to solve in the worst case. Presburger arithmetic is a logic that allows statements involving positive integers, variables taking positive integers as their values, the addition operation +, the equality symbol = and quantifiers and , as well as all the connectives such as and, or etc.
For example, X [ if ~( X = 1 ), then Y Z [ X = Y + Z ] ] is a proposition of Presburger arithmetic.

In Presburger arithmetic (minus addition operation), if, in addition, sets of integers and the predicate "belongs to" (an element X belongs to a set S) are allowed, the logic is called WS1S (Weak Second-order theory of 1 Successor). For the satisfiability problem of WS1S, there are no K-fold exponential time algorithms to solve it for any number K. Such a problem (having no K-fold exponential time algorithms) is called nonelementary.

Now let us go back to the satisfiability problem of propositional logic. This problem belongs to a peculiar class of problems called NP-Complete problems. For the problems of this class there are no known polynomial time algorithms for solving them nor are they known to be unsolvable with polynomial time algorithms. At the moment, however, the consensus is that they ca not be solved with polynomial time algorithms. Below we are going to characterize this class of problems.

First, there are problems that are solved by answering with yes or no. For example, "Is a string w in the language a*b ? ", "Is it possible to schedule committee meetings without conflicts into a given number of time slots ? " , " Is it possible to assign colors to vertices of a given graph using a given number of colors or less so that no two vertices connected directly by an edge have the same color assigned ? " etc. These problems are called decision problems. Some of these decision problems are NP-complete problems.
Let us here review nondeterministic Turing machines. Consider the problem of coloring vertices of a graph with a given number of colors or less so that no two vertices connected directly by an edge have the same color assigned. This problem is called "Graph Coloring" problem or more precisely "Vertex Color" problem. Let us try to solve the following instances of this graph coloring problem:

Given the following graph, is it possible to color its vertices with three or less colors ?




                           



For the graphs of (a) and (b), you could find a solution very easily by inspection. You could see a right coloring as soon as you saw the graphs. However, you can most likely not tell how you arrived at your solutions. You probably don't have any algorithms you could use to solve them. You could somehow see the solutions. This is basically the idea of nondeterministic (Turing) machine. There is no fixed procedure which you can use repeatedly to solve instance after instance of this problem. But you can somehow solve them.
Let us move on to a slightly more complex example of (c). For this graph to find a right coloring you could start with vertex 1 and assign color a. Then move on to vertex 2 and assign color b(it has to be something other than a ). Then go to vertex 3 and assign a third color, say c. Then at vertex 4 select color b and for vertex 5 use color a.
In this process we make a decision as to what color to use for each vertex and when a decision is made for all the vertices we have a solution to the problem. This process applies to any decision problem. That is to solve a decision problem a number of smaller decisions are made one after another and as a result a solution to the problem is obtained. This process can be represented by a tree called decision tree. For example, for the graph coloring problem let us first decide on the order of vertices we color in, say 1, 2, 3, 4 and 5 for the graph of (c) above. Then the root of its decision tree corresponds to the vertex we assign a color to first (vertex 1 in this example). Then for each possible color for the first vertex, a child is created for the first vertex of the tree. So the second level of the decision tree corresponds to the second vertex to be colored. Then in general, for each possible color for each vertex of level i of the decision tree, a child is created. Those children form level i+1 of the decision tree. The decision tree for the graph of (c) is given below. Since any color can be assigned to vertex 1 without loss of generality, it has just one child in the actual decision tree. Also since in this case the i-th and (i+1)-th vertices are connected by an edge for i = 1, 2, 3, 4, they can not have the same color. So each vertex after vertex 1 has two colors to choose from. So they each have two children in the decision tree.




                           




Thus during the process of solving the problem a decision is made at each level and when all levels are covered, the problem is solved. A path from the root to a leaf corresponds to a coloring of the vertices of the given graph. A decision tree, however, does not tell us how to make decisions. Also a decision tree does not tell how to order the vertices for coloring, that is which vertex to color first, second etc.
A deterministic machine (or algorithm) has a specific fixed set of rules for making a decision at each level of the decision tree. Although it knows what to do at every stage of problem solving, the decisions it makes are not necessarily the right ones. When it makes wrong decisions, it must retract earlier decisions and try different paths, which is called backtracking.
For the graph coloring problem a deterministic algorithm might first order the vertices of the graph in decreasing order of their degree and also order colors. Then, following the order of the vertices, assign to each vertex the highest order color available for the vertex. Since that kind of algorithm is not guaranteed to use the minimum number of colors, it may produce a wrong answer unless there is some provision for backtracking.
A nondeterministic (Turing) machine, on the other hand, is a fictitious machine and somehow knows which branch (child) to select at each step. It always makes a right selection.

A decision problem is said to belong to class NP if each vertex in its decision tree has a finite number of children and if it can be solved by a nondeterministic (Turing) machine in polynomial time.
The graph coloring problem is in class NP, so are the satisfiability problem for propositional logic and most of the scheduling problems just to name a few. Also there are other characterizations of class NP. Interested readers click here.
At this moment it is not known whether or not problems in class NP can be solved with a polynomial time algorithm in the worst case. The consensus is that there is no polynomial time algorithm to solve them. It would take at least exponential time. Among the problems in class NP, there are problems which all problems of class NP can be transformed to in polynomial time. Those problems are called NP-complete problems. If a polynomial time algorithm is found for any one of the NP-complete problems, all the problems in NP can be solved in polynomial time. Below we are going to study NP-complete problems. We start our discussion with the concept of polynomial time transformation (reduction). Basically we say a decision problem Q1 is polynomially reducible to a decision problem Q2 if and only if there is a transformation that transforms any arbitrary instance of Q1 into an instance of Q2 in polynomial time such that the answer to Q1 is yes if and only if the answer to Q2 is yes.
A little more formally we define this in terms of languages. Note that a decision problem can be viewed as a language of its instances and that solving it can be considered as recognizing the language as we have seen earlier.

Let L1 and L2 be languages over alphabets 1 and 2, respectively. We say that L1 is polynomial-time reducible to L2 if and only if there is a function f from 1* to 2* such that for any string x 1* , x L1 if and only if f(x) L2 and f can be computed in polynomial time.

For example let us consider the following two problems: graph coloring and scheduling of committee meetings.

The graph coloring problem is as given above. In the scheduling of committee meetings problem, committees with their members and a positive integer k are given. The problem is whether or not the meetings of the committees can be scheduled in k or less time slots so that everyone can attend one's meetings. Note that some people may be in more than one committee.

Let us try to show that this scheduling problem is polynomial time reducible to the graph coloring problem.
What we need to do is given an instance of the scheduling problem construct an instance of the graph coloring problem, that is construct a graph and give the number of colors to be used to color its vertices so that the meetings can be scheduled if and only if graph can be colored.
Let us consider the following transformation:

For each committee add a vertex to the graph, and if and only if two committee have some members in common, connect with an edge the vertices corresponding to the committees. Then the meetings can be scheduled in k or less time slots if and only if the graph can be colored with k or less colors.
For example suppose that we are given the committees 1, 2, 3 and 4 with the memberships { a, b }, {a, c, d }, { b, d } and { a, c }, respectively. Suppose also that k = 3. Thus the scheduling problem asks whether or not the meetings of the given committees can be scheduled in 3 time slots without any conflicts.
The corresponding graph for the graph coloring problem can be constructed as follows:
Corresponding to the committees 1, 2, 3 and 4, add vertices 1, 2, 3 and 4 to the graph. Then since committees 1 and 2 share a, an edge is inserted between vertices 1 and 2. Similarly since committees 1 and 3, and 1 and 4 share members, edges are added between 1 and 3, and 1 and 4. Proceeding similarly the following graph is obtained corresponding to the committee memberships.




                           




Suppose that the meetings can be scheduled in p time slots, where p k. Then the committees can be grouped into p groups so that the committees in the same group can meet at the same time. Corresponding to this grouping assign colors to the vertices of the graph so that the vertices in the same group are given the same color and those in different groups are given different colors. This coloring uses p colors which does not exceed k, and vertices connected with an edge have different colors. For if any two vertices are connected with an edge, then that means that the corresponding committees share some members and that they are scheduled to meet in different time slots. Thus these two vertices must get different colors.
Conversely if the graph can be colored with k or less colors, then it can be easily seen that the committees can meet in k or less time slots.
It is also easily seen that the transformation, that is the construction of graph for a given set of committees, can be done in time polynomial in the size of the problem, which in this case can be taken as the number of committees.

We are now ready to discuss NP-completeness.

It was first proven by S. Cook that the problems of class NP can be polynomial time reducible to the satisfiability problem of propositional logic. Subsequently the satisfiability problem was found to be polynomial time reducible to many other problems. As a consequence if a polynomial time algorithm is found for any one of those problems, all the problems can be solved with polynomial time algorithms. This group of problems are called NP-complete problems. Formally a problem is NP-hard if every problem in class NP can be polynomial time reducible to it. A problem is NP-complete if it is in class NP and NP-hard.
It can be easily seen that if a problem P at hand is NP-hard and if a problem known to be NP-complete can be polynomial time reducible to P, then P is also NP-complete. For all the problems in class NP can be reduced to P through the known NP-complete problem in polynomial time.
If a problem is NP-complete, then the consensus today is that it is most likely that no polynomial time algorithms i.e. fast algorithms exist to solve it.

Today hundreds of problems are known to be NP-complete. Some of them are listed below.

NP-complete Problems

  1. Satisfiability Problem for Propositional Logic
  2. Graph Color Problem
  3. Committee Meeting Schedule Problem
  4. In fact most scheduling problems are NP-complete.
  5. Traveling Salesman Problem
  6. Given cities and traveling times between cities, a traveling salesman wants to know a shortest route to visit all cities exactly once and come back to where he/she started.
  7. Bin Packing Problem
  8. Given a set of objects, their sizes and a number of bins of the same size, find out whether or not the objects can be put into the bins.
  9. Partition Problem
  10. Given a set of integers, group them into two groups so that the sum of the numbers of one group is equal to that of the other group.
  11. Subgraph Isomorphism Problem
  12. Given two graphs, find out whether or not one is a subgraph of the other.
  13. Set Cover Problem
  14. Given a set S, a collection of subsets of S and an integer k, find out whether or not there are k or less subsets in the collection whose union is S.
  15. Knapsack Problem
  16. Given a knapsack of size S, a set of objects, their sizes, their values and an integer V, is it possible to select objects so that the sum of their sizes does not exceed S and the sum of their values is V or larger ?
  17. 3-Dimensional Matching
    Given three sets A, B and C of the same size, and a subset S of the Cartesian product A X B X C.
    Is there a subset T, called a matching, of S such that every element of A, B, and C appears exactly once in T ?

    For example, let A = {1,2}, B = {a,b}, and C = {x,y}, and S = {(1,b,x),(1,b,y), (2,a,x), (2,b,y)}.
    Then T = {(1,b,y), (2,a,x)} is a desired set satisfying all the requirements. Note that {(1,b,x),(2,a,x)} is not a matching.



Test Your Understanding of Time Complexity of Decision Problem

Indicate which of the following statements are correct and which are not.
Click True or Fals , then Submit.







Back to Study Schedule

Back to Table of Contents







~