# P Vs. NP Problem: The Greatest Unsolved Problem In Mathematics And Computer Science

1404 Words 6 Pages
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  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,

## Related Documents

• Words: 10008 - Pages: 41
• Words: 2185 - Pages: 9
• Words: 2022 - Pages: 9
• ## Modern Day Algebra Essay

And, even though nowadays, algebra is a rather abstract mathematics, this was not always the case. It was through centuries of work from remarkable individuals with an undying passion and curiosity that algebra slowly but surely evolved. Introduction In modern day mathematics, the term algebra denotes the manipulation of abstract symbols, solving equations for unknowns, simplifying expressions, or simply…

Words: 1237 - Pages: 5
• Words: 2427 - Pages: 10
• ## Philosophy Of Education Research Paper

What is so fascinating to me is that there are a lot of problems in mathematics that have a long way and a short way to solve the problem. The long way teaches you the concept and gives you a complete understanding of the problem. The short way helps you do the problem faster and efficiently and the short way is sometimes mind-blowing. Above, is the definition I gave of mathematics before I entered into this program. Now I would like to discuss the importance of mathematics.…

Words: 1178 - Pages: 5
• Words: 2064 - Pages: 9
• ## How Programming Changed My Life

My problem solving skills have been greatly influenced by my time spent programming. Programming is all about breaking problems down into simpler parts. You look for pieces of the problem that recur, create solutions for those, and then combine the individual, simpler parts to solve the problem as a whole. This mirrors how I look at problems now. I try find simple parts of a problem, and solve them first.…

Words: 1169 - Pages: 5
• ## What Is Square Shaped Structure Analysis

In first step we was modeling and analyzing some square shaped structure with ABAQUS and used results to solve finite-element partial differential equation adaptive to structural analysis. r r t ve a fini l mesh g er ormul n ruc ral analys i to e n sic equ eri lly. Follo la e s ur lem ̈ ( + ) − + − ̈ = 2. In the 2nd step, we start improving our Kohonen algorithm by using Computer Programming and Math softwares MATLAB and STUDIO-1. During this step, the network must be fed a large number of example vectors that represent the kinds of vectors expected during mapping.…

Words: 1393 - Pages: 6