Home | Conferences | Techknowledge | 9th National Conference | Towards The Solution Of NP Complete Problems

Towards The Solution Of NP Complete Problems

By
Font size: Decrease font Enlarge font

The word algorithm is the magical word in the field of computer science because the imagination of the existence of any branch of computer science like artificial intelligence, computer network, human computer interaction etc. is useless without the word algorithm. There are some problems for which no any researcher is able to design those algorithms, which have polynomial time complexity in the worst case. No any researchers have even proved that no any polynomial time algorithm can solve them in worst case. NP complete problems arise in domains like automata and language theory, sequencing and scheduling, mathematical programming, algebra and number theory, games and puzzles, optimization problems, Boolean logic, graphs, arithmetic, designing of network, sets and partitions, storage and retrieval, biology, chemistry, physics etc. In this paper such kind of the problems (non deterministic polynomial type complete problem) is being studied along with the approximation algorithm for vertex cover problem. Researchers are applying their best efforts to design new approximation algorithms for nondeterministic polynomial type problems which have comparable less time complexity and space complexity as compared to the existing approximation algorithms.

1.    Introduction
An algorithm may be defined as any computational procedure    which   takes the input as a single value or set of values and produces the output as a single value or set of values [2]. As   it   is well known fact that all problems can  not be solved in the polynomial time in the worst case. If n is the size of  the input and those algorithms which have the time complexity of O(nk) in the worst case are known as polynomial time algorithms. There are some problems which cannot be solved by   polynomial time algorithms in the worst case. For example, there are problems such as Turing's famous "Halting Problem," which  cannot be solved by any computer in the polynomial time. Tractable problems are those problems which can be solved in time O(nk) for any constant k. But those problems that require super polynomial time are known as intractable or hard problems.

 No polynomial-time algorithm exist   for an NP-complete problem and  no any researcher has yet been able to prove that no polynomial-time algorithm can exist for any one of them. Several   NP complete problems   seem similar to polynomial-time algorithms. In each of the following pairs of problems, the first problem is solvable in polynomial time but   the other is not solvable in the polynomial time.
Shortest path problems can  be solved in the polynomial time. If in a particular graph some edge has negative weight, even then we can find shortest paths from a single source in a directed graph G = (V, E) in O(VE) time. Where V represents the set of vertices and E represents the set of edges. But for finding the longest simple path between two vertices cannot be solved in the polynomial time in the worst case. So the problem of finding the longest simple path between two vertices is NP-complete. If the weight  of all the edges are unity even then it is NP-complete problem.
An Euler path   of a connected, directed graph is a path that traverses each edge of graph   exactly once, although it may visit a vertex of graph  more than once. If E represents the set of edges and V represents the set of vertices then we can determine whether a graph has an Euler tour in only O(E) time complexity. A Hamiltonian cycle of a directed graph is a  path  that traverse each and exactly every vertex of the graph exactly once . As there is no known polynomial time algorithm which can find the Hamiltonian cycle of graph  G=(V,E) in the polynomial time. So the problem of   determining whether a directed graph G=(V,E) has a Hamiltonian cycle is NP-complete problem.
2-CNF satisfiability  problem can be solved in the polynomial time  but  3-CNF satisfiability problem can not be solved in the polynomial time so 3-CNF satisfiability is NP complete problem.

2.    Related Work:  If n is the size of the input and those algorithms which have the time complexity of O(nk) in the worst case are known as polynomial time algorithms. All  problems cannot be solved by the polynomial time algorithms in the worst case.
Those problems that are "verifiable" in polynomial time are    known to be in   class NP problems. If "certificate" of a solution  is being given and  if we can verify that the certificate is correct in polynomial time in  the size of the input to the problem, then the problem is said to be in class of NP problems . Any problem in P is also in NP. It is well known fact that   if any one of the existing   NP-complete problem can be solved in polynomial time, then   every NP-complete problem can be easily solved by  polynomial-time algorithm. Most computer researchers believe that the NP-complete problems are intractable, because there are large  number of NP complete problem and researchers have applied their best efforts   to solve these problems in the polynomial time but no any researcher got the success to give the polynomial time algorithms which can give the optimum solution to such kind of the problems for such kinds of the problems.
As there is no any existing   algorithm which   can give optimum solution to  NP complete problems in polynomial time in the worst case. So researchers gave  approximation algorithm to solve such kind of    NP complete problems in polynomial time in the worst case. Approximation algorithms give the approximate solution to a particular problem    which is close to the optimal solution to the   problem. The techniques which is being used to  show a particular problem to be NP-complete  is different  from the techniques used to design and analyze algorithms because in showing a problem to be NP-complete, we are making a statement about how hard is the problem .
There are   some    problems that require time as Θ(n1000). It is well known fact   that when an algorithm which has polynomial time complexity for a problem is being discovered for a problem by a researcher, it is likely that an algorithm with the less time complexity will be discovered in the near future. Also a problem which is solvable in polynomial time in one model can  also be easily solved in polynomial time in another  model. For example, the   problems solvable in polynomial time by the serial random-access machine are also solvable in polynomial time on abstract Turing machines. Those   problems    which are solvable in   polynomial     time has also closure properties because   polynomials are closed under addition, subtraction,   multiplication and composition. If any of the polynomial-time algorithms makes a fixed number of calls to subroutines   which have running time of polynomial time, the running time of the composite algorithm is also polynomial because polynomial time solvable problem has closure properties. An alphabet Σ is set of symbols of finite number of elements.  language   over Σ is any set of strings which is being made up  of symbols from Σ. For example if Σ = {0, 1}, the set L = {11110, 1111, 11001, 11001, 100011, 100101, 11,...} is the language of binary representations of numbers. An  empty string is being represented  by ε, and the empty language  is being represented by Ø. Every language L over Σ is a subset of Σ*.
There are  a variety of operations on languages. Some theoretic operations, such as union and intersection, can be apply to the languages. Generally we can say that an algorithm A accepts a string y if y is being given as input, the algorithm's output A(y) is 1. An algorithm A rejects a string y if and only if   A(y) = 0. Any  language L is said to be acceptable in polynomial time by an algorithm A if it is accepted by A and if in addition there is a constant k such that for any length-n string which is an element of  L, algorithm A accepts x in time O(nk). As some problems can   be    easily solved by the optimization algorithms in the   polynomial time in the worst case. For example all pair shortest path problems can be solved by Floyd Warshall’s algorithm which has the time complexity of O(n3 ). But there are still some problems which can not   be solved by the optimization algorithm in the polynomial time in the worst case. So researchers gave large number of approximation algorithm to solve such kind of the problems. Approximation algorithm gives the solution  which is approximate to the optimal solution of the problem and approximation algorithms have polynomial time complexity in the worst case. Examples of NP complete problems are traveling salesman problem, subset sum problem, vertex cover problem etc. Researchers are applying their best efforts to design new approximation algorithms, which have comparable less time complexity as compared to the existing approximation algorithms. Many  NP-complete problems are of practical use but we cannot  abandon these NP-complete problems merely because there is no any optimization algorithm which can solve these problems in the polynomial time in the worst case. If the actual inputs of particular problems are small, an algorithm which has exponential running time may be satisfactory. We may be able to isolate those special cases that are solvable in polynomial  time.  It may still be possible to find solutions which is approximate the exact solution  in polynomial  time  in the worst case. As it is well known fact that near-optimality solution is  good enough. An algorithm that returns the   solutions  which is approximate to the optimum solution is called an approximation algorithm. In maximization problem, we want to maximize the value of output to a particular problem while in the case of minimization problem we want to minimize the value of output to a problem. Let C be the cost of the solution   which is being produced by an approximation algorithm and C* be the cost of the solution   which is being produced by an optimization algorithm. Then  approximation ratio of ρ(n) of size n, the cost C of the solution produced by an approximation algorithm is within a factor of ρ(n) of the cost C* which represents the cost of the optimal solution. The definitions of approximation ratio apply for both maximization and minimization problems both. For a maximization problem, 0 < C ≤ C*, The   ratio C*/C gives the factor by which the cost of an optimal solution   which is obtained by the optimization algorithm is larger than the cost of the approximate solution which is obtained by the approximation algorithm. But for a minimization problem, 0 < C* ≤ C, and the ratio C/C* gives the factor by which the cost of the approximate solution   which is being obtained though the approximation algorithm is larger than the cost of an optimal solution which is obtained through the optimization algorithm. As it is being assumed that all costs are positive, so these ratios are always well defined. The value of approximation ratio of an approximation algorithm is never less than 1.  When the value of approximation ratio is one, it means the   optimal solution is being given by that algorithm. If the value of approximation ratio is close to one it means the solution    which is being given by the  approximation algorithm   is close to the optimal solution and vice versa. 
Researchers have already designed the   polynomial-time approximation algorithms   for some problems which have  small constant approximation ratios. while for other problems, the best known polynomial-time approximation algorithms have approximation ratios that grow as functions of the input size n. In   the set-cover problem if the size of  the input increases then the approximation ratio grows and vice versa. There is a trade-off between computation time and the quality of the approximation.
An approximation scheme is an approximation algorithm that takes as input  an instance of the problem as well as also a value €>  0 such that for any fixed €, the scheme is a (1 +€ )-approximation algorithm. Vertex-cover problem is  an NP-complete minimization problem. The traveling-salesman problem an NP-complete minimization problem in which the cost function   may satisfy or may not satisfy  the triangle inequality. The vertex-cover problem was defined and proven to  be NP-complete. In vertex-cover problem the goal   is to find a vertex cover of minimum size in a given undirected graph. An   approximation algorithm  which takes as input an undirected graph G=(V,E) and returns a vertex cover.  As vertex cover is the minimization problem in which goal is to select the minimum number of vertices from an undirected graph which can cover all the edges of the graph G.
An approximation algorithm for vertex cover problem
If G=(V,E) be the given graph.
If X represents an  initially   empty set.
E[G] represents the set of all edges in the graph G=(V,E).
1 X ← Ø
2 E′ ← E[G]
3 while E′ ≠ Ø
4            let us consider (a, b) be an  edge of E′
5           X ← X U{a, b}
6            remove from E′ every edge incident on   
              either a or b
7 return X
The above algorithm returns the set X which is the set of the vertices.
If adjacency lists is to be used to  represent E′ then the running time of this algorithm is O(V + E).Researchers are applying their best efforts to design the new approximation algorithms for NP complete problems like vehicle routing problems with time windows, deadline traveling salesman problem, orienteering problems, subset sum problem, vertex cover problem, set cover problem, prize collecting traveling salesman problem etc.  In  Vehicle Routing with Time-Windows problem, a graph G=(V,E) is being given with n number of vertices and  each node v also has a release  time R(v) and a deadline D(v) and a person starts his visit from the starting node r and the goal  of that person is to visit maximum number of vertices with in their time windows [R(v),D(v)]. But in deadline traveling salesman problem, the releasing time for every vertex is 0 and the goal is to visit the maximum number of vertices with in their deadlines.  In [34]an approximation algorithm for Deadline-TSP is being given which has time complexity of O(log n)  and then they extended this algorithm to design an  approximation algorithm for the Time-Window problem which has the time complexity of O(log2 n).

3.    Conclusion: In this paper,   a study on NP complete  problems along with the approximation algorithm for  NP complete problems like vertex cover problem  is being given and concluded  that scientists are applying their best efforts to design approximation algorithms for nondeterministic polynomial type problems which  have less time complexity and space complexity  as compared to the previously  existing algorithms and they are getting the success also in this field.

4. References:
1.    E. Horowitz and S. Sahni, (1982) "Fundamental of Computer Algorithms", Computer Science Press.
2.    T. Cormen, C. Leiserson and R. Rivest, (1991) "Introduction to Algorithms", MIT Press.
3.    A.V. Aho, J.E. Hopcroft and J.D. Ullman, (1974) "The Design and Analysis of Computer Algorithms", Addison-Wesley.
4.    A.V. Aho, J.E. Hopcroft and J.D. Ullman, (1984) "Data Structures and Algorithms", Addison-Wesley.
5.    S. Baase, (1988) "Computer Algorithms: Introduction to Design and Analysis", Addison-Wesley.
6.    L. Banachowski, A. Kreczmar and W. Rytter, (1991) "Analysis of Algorithms and Data Structures".
7.    R. Baeza-Yates, "Teaching Algorithms",(1995) IV Iberoamerican Congress on Computer Science Education, Canela, Brazil.
8.    J. Nievergelt and K. Hinrichs, (1993) "Algorithms and Data Structures with Applications to Graphics and Geometry", Prentice-Hall.
9.    G- Brassard, and P. Bratley, (1988) "Algorithmics: Theory and Practice", Prentice-Hall, 1988.
10.    E.M. Reingold, J. Nievergelt and N. Deo, (1977) "Combinatorial Algorithms: Theory and Practice",Prentice-Hall.
11.    H. Will, (1986) "Algorithms and Complexity", Prentice-Hall.
12.    M. Crochemore and W. Rytter, (1994) "Text Algorithms", Oxford Press.
13.    J.S. Vitter and P. Flajolet", (1990)"Average-case analysis of Algorithms and Data Structures", Handbook of Theoretical Computer Science (volume A), Elsevier and MIT Press, pp 431-524.
14.    F.P. Preparata and M.I. Shamos. (1985) "Computational Geometry: An Introduction", Springer Verlag.
15.    W. Frakes and R. Baeza-Yates, editors, (1992) "Information Retrieval: Data Structures and Algorithms",Prentice-Hall.
16.    A. Gibbons and W. Rytter, (1988) "Efficient Parallel Algorithms", Cambridge University Press.
17.    U. Manber, (1989) "Introduction to Algorithms: A Creative approach", Addison-Wesley.
18.    G. Gonnet and R. Baeza-Yates, (1991) "Handbook of Algorithms and Data Structures", Addison- Wesley.
19.    Blaine A. Price, Ronald M. Beacker and Inn S. Small, A Principled Taxonomy of Software Visualization, Journal of Visual Languages and Computing 4, pp 211-266,.

  • Email to a friend Email to a friend
  • Print version Print version
  • Plain text Plain text

Tagged as:

No tags for this article