Journal of Applied Computer Science & Mathematics (Jan 2010)

Towards the Solution of NP Complete Problems

  • Amit Kumar,
  • Pawan Jindal

Journal volume & issue
Vol. 4, no. 9
pp. 63 – 66

Abstract

Read online

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.

Keywords