MbShea@PWP@English@UMCP

Abstract:
P vs NP is a major unsolved problem in computer science that would have immense implications. This deals with the solvability of any problem and how fast an algorithm can be executed. A problem is in class P if an algorithm can find a solution in polynomial time (as opposed to a slower running time, such as exponential). A problem is in class NP if given a possible solution as input, an algorithm can verify in polynomial whether the input solves the problem. Sudoku, for example, is clearly in NP since checking whether a completed board is valid or not is simple and quick. Writing an algorithm to solve Sudoku boards from a starting position, however, is much more tricky. If a problem is in P, then the problem is also in NP since solving the problem is always more complicated than verifying a solution. However, no one knows whether the converse is true or not. This gives rise to major question: does P = NP? That is, if a problem has solutions that can be quickly verified, can the problem itself be quickly solved? Most computer scientists believe this is not true, although no formal proof has been formulated. This is due to the efficiency of algorithms: for complex problems, better algorithms may exist but not yet been discovered.

WC = 221

Reader’s Profile:
Someone who has no interest in computers or science or complex mathematical proofs would find this boring and have a “who cares” attitude.

Reader’s Response:
It seems pretty obvious to me that solving problems is harder than verifying solution. You also make this seem like it’s super important and will have some huge critical impact on society when in reality it’s just another math paper. It sounds way too general to have any real solution and you should focus your efforts on things more practical and innovative for society.

Thesis:
The P vs NP problem questions whether for a given problem, if a particular solution can be verified relatively quickly, then the problem itself can also be solved relatively quickly. Most computer scientists believe that this is not true, but no formal proof has been created, primarily due to the complex nature of the problem. In fact, the problem is so complicated that I have found that many explanations of P vs NP are very technical and difficult to understand. Therefore, I want to provide a clear explanation and a general overview of P vs NP to those who have some understanding of computer science but not necessarily enough to formulate a proof.

Voice:
3rd person for most, maybe 1st person if I describe why I am writing this.

Citation:
APA citations throughout.

L, you can open this analysis with a first person note of introduction, where you address "why."

Then, the rest of the analysis can rest in third person voice.

Also, ask me about Polya. I poked around and found this lecture slide set that opens with a P NP discussion and later spend time on Polya's problem solving method. Enjoy. And, ask my about how I know Polya.

http://www.cs.toronto.edu/~capestim/csc104/csc104s11/ProblemSolving.pdf