Abstract— The P vs NP problem is still one of the greatest unsolved problem in Mathematics and computer Science. This survey paper is intended to explain what P vs NP problem is and what are the advances that have been made to solve this problem and How closer are we to solve this problem and what is its status i.e. Is P = NP?
Keywords— Polynomial, Non - Determinsitic, P, NP, NPC Reductions, Reducibility, Reductions, certificate, complexity
I. INTRODUCTION
What is P vs NP? Why it is important to know what problems are in P and what problems are in NP? Some problems like Addition, Subtraction, sorting and algorithms such as Dijkstra’s are all belong to the category of P. The problems that are solved in polynomial time. But there are problems …show more content…
.
III. PERVASIVE NP COMPLETE PROBLEMS
NP complete problem occurs in almost every domain of Mathematics and computer science such as Boolean Algebra and logic, Graph Theory, Theory of Automata, Set Theory, Algebra and Number theory and so on. Its application are used in Computer Science, Biology, Chemistry, Physics etc. To understand NP complete problems and their reduction, Clique problem is presented and proved as NP Complete. The notion of NP Completeness was proposed by Cook in 1971and they gave the first NP completeness proof for formula satisfiability and 3-CNF. Levin independently also defined this notion by giving the proof of Tiling problem. Below figure describes how to go about doing a reduction from a new problem to a problem already given.
IV. CURRENT STATUS OF P AND NP …show more content…
It would help in giving a formal proof to the problems that cannot be solved efficiently, so that researchers can focus their attention on either giving partial solution to the problems or solution to other problems that remains to be solved. L.R. Foulds [] in his paper “The Heuristic Problem solving approach” discusses heuristic approaches (approximate approaches) to solve problems which are NP Hard. Heuristic and Average case analysis can solve many NP- complete problems efficiently. The study of NP complete problems does the worst case analysis of a problem. But, the specific problems can be solved without worst case analysis. Leonid Levin [7] designed efficient algorithms for distributional version of P and NP.
If a problem is NP-complete then there is least possibility to find its polynomial time solution. However, it is still possible to find the near optimal solutions in Polynomial Time. Now, there are approximate algorithms for thousands of NP Complete Problems such as Vertex Cover, Travelling Salesman Problem, Max 3-CNF Satisfiability problem, subset sum problem etc. The algorithm APPROX-TSP-TOUR is given in paper by An Analysis of Several Heuristics for the Traveling Salesman Problem by Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis,
Keywords— Polynomial, Non - Determinsitic, P, NP, NPC Reductions, Reducibility, Reductions, certificate, complexity
I. INTRODUCTION
What is P vs NP? Why it is important to know what problems are in P and what problems are in NP? Some problems like Addition, Subtraction, sorting and algorithms such as Dijkstra’s are all belong to the category of P. The problems that are solved in polynomial time. But there are problems …show more content…
.
III. PERVASIVE NP COMPLETE PROBLEMS
NP complete problem occurs in almost every domain of Mathematics and computer science such as Boolean Algebra and logic, Graph Theory, Theory of Automata, Set Theory, Algebra and Number theory and so on. Its application are used in Computer Science, Biology, Chemistry, Physics etc. To understand NP complete problems and their reduction, Clique problem is presented and proved as NP Complete. The notion of NP Completeness was proposed by Cook in 1971and they gave the first NP completeness proof for formula satisfiability and 3-CNF. Levin independently also defined this notion by giving the proof of Tiling problem. Below figure describes how to go about doing a reduction from a new problem to a problem already given.
IV. CURRENT STATUS OF P AND NP …show more content…
It would help in giving a formal proof to the problems that cannot be solved efficiently, so that researchers can focus their attention on either giving partial solution to the problems or solution to other problems that remains to be solved. L.R. Foulds [] in his paper “The Heuristic Problem solving approach” discusses heuristic approaches (approximate approaches) to solve problems which are NP Hard. Heuristic and Average case analysis can solve many NP- complete problems efficiently. The study of NP complete problems does the worst case analysis of a problem. But, the specific problems can be solved without worst case analysis. Leonid Levin [7] designed efficient algorithms for distributional version of P and NP.
If a problem is NP-complete then there is least possibility to find its polynomial time solution. However, it is still possible to find the near optimal solutions in Polynomial Time. Now, there are approximate algorithms for thousands of NP Complete Problems such as Vertex Cover, Travelling Salesman Problem, Max 3-CNF Satisfiability problem, subset sum problem etc. The algorithm APPROX-TSP-TOUR is given in paper by An Analysis of Several Heuristics for the Traveling Salesman Problem by Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis,