Complexity
Time Complexity
Subjects to be Learned
- Time Complexity of Problems
- Decision Tree
- Class NP
- Polynomial Time Transformation
- NP-Complete Problems
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
- Satisfiability Problem for Propositional Logic
- Graph Color Problem
- Committee Meeting Schedule Problem
In fact most scheduling problems are NP-complete.
- Traveling Salesman Problem
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.
- Bin Packing Problem
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.
- Partition Problem
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.
- Subgraph Isomorphism Problem
Given two graphs, find out whether or not one is a subgraph of the other.
- Set Cover Problem
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.
- Knapsack Problem
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 ?
- 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