Objective & Criteria:
Assignment 1.3 is a practice for students to break down a relatively complex term into a parenthetical definition, a sentence definition, and an expanded definition.
Situation & Audience:
A Software Developer explaining the P versus NP Problem
Term:
P versus NP Problem
Parenthetical Definition:
The P versus NP problem is a significant unsolved problem in computer science.
Sentenced Definition:
The P versus NP problem poses the question of whether every problem whose solution can be verified, can also be solved quickly. A question is either P (polynomial), which means that it is easy to solve, or it is NP (non-deterministic polynomial), which means that it is easy to verify but hard to solve.
Expanded Definition:
P vs. NP deals with the gap between computers being able to quickly solve problems against just being able to test proposed solutions for correctness. P problems are easily solved by computers. In contrast, NP problems are not easily solvable, but if presented with a solution, it is easy to verify its correctness.
Currently, it appears that P ≠ NP, meaning we have plenty of examples of problems that we can quickly verify potential answers to, but that we can’t solve quickly. Here is an example question:
- A farmer wants to take 100 watermelons of different weights to the market. She needs to pack the watermelons into boxes. Each box can only hold 20 kilograms without breaking. The farmer needs to know if 10 boxes will be enough for her to carry all 100 watermelons to market. [1]
Current and Hypothetical Situation of Pvs NP [2]
To solve this problem, you have to try all the millions of combinations. Hence the P vs. NP problem is the search for a way to solve problems like this without actually having to try each time-consuming combination.
This is why the answer to the P versus NP problem is so interesting to people. If anyone were able to show that P is equal to NP, it would make difficult real-world problems trivial for computers and would have profound effects on computing, and therefore on our society.
Works Cited:
[1] Daniel Miessler. “P Vs. NP Explained.” Daniel Miessler, 1 Nov. 2017, danielmiessler.com/study/pvsnp/.
[2]Aamir, Bilal. “P Vs NP Problem In A Nutshell.” Medium, Medium, 25 Mar. 2019, medium.com/@bilalaamir/p-vs-np-problem-in-a-nutshell-dbf08133bec5.
Hardesty, Larry. “Explained: P vs. NP.” MIT News | Massachusetts Institute of Technology, news.mit.edu/2009/explainer-pnp.
Leave a Reply