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.
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.