P vs MP - What does it Mean?
Computer Science is based around the idea of using
algorithms to solve a wide variety of problems. Most problems you can think of
can be translated into a program and run by a computer. However, there are a
few theoretical problems in Computer Science which continue to remain unsolved;
one of these problems is whether P = NP. It has yet to be solved and you can
get paid 1 million dollars for solving it but what does it mean? Well in this
equation, P stands for polynomial and NP stands for nondeterministic polynomial time. These basically refer to
types of problems and the time it takes to solve them. NP
represents problems whose solutions can be verified relatively quickly but
takes a very long time to actually solve the problem. A good example that Larry Hardesty
gave for MIT news is finding prime factors of a number. All you need to to to
verify a solution is multiply these numbers together, but to actually solve the
problem a program has to look at individual numbers and test them until it
finds a solution. this example is actually one way that online information is protected. So the question
posed by the equation is if a problem exists that takes a relatively short
amount of time to check, does it also take a short amount of time to solve? This problem
is particularly important to online security, which uses cyphers and code to
protect data. The solution to a cypher can be checked easily – just see if you
can get past a security system, but solving this problem takes a long long
time. The time it takes to solve these problems (depending on the problem it
could take years and years to finally solve) is what makes it secure. However,
if there is a way to solve a problem like this in the same timeframe it takes
to verify its solution, it would greatly change how we use computers to solve
problems.sources:
http://news.mit.edu/2009/explainer-pnp
http://www.claymath.org/millennium-problems/p-vs-np-problem
https://www.theguardian.com/technology/2013/sep/05/how-internet-encryption-works
I find it interesting that many archaic and even some modern security systems are predicated on what may seem like simple codes to solve but take vasts amount of time to computationally do. One example that comes to mind is the RSA crypto system, which requires finding very large prime numbers to bypass.
ReplyDeleteInteresting post. As I read it, I was immediately reminded of a blog post I wrote last month about the Boolean Pythagorean triples problem that was similarly impossible to solve, until a supercomputer at the University of Texas did the job. Even then, though, the prize money was only $100. I feel like a supercomputer could solve this problem if given an ample amount of time--then again, I could be wrong.
ReplyDeleteHere's the URL to my post if you're interested:
http://codemonkeychronicles.blogspot.com/2016/10/the-boolean-pythagorean-triples-problem.html