## [intro-to] P vs. NP

NOTE: The following article is intended as a gentle introduction
for the subject, so I have intentionally left out some information that I considered
is out of scope. However, if you are familiar with the subject and if you think
I presented *factually wrong* statements, I will greatly appreciate an email
with corrections. Also, if you are confused with my explanation, please feel free to
send me an email with details of where you are confused, so I can make it a bit
more clear.

# What exactly are P and NP? Why do we need them?

In order to understand the P vs. NP problem, we must understand P and NP first. P
and NP rose from the necessity of matheticians and computer scientists to
describe how much resources, such as time, are needed to solve a decision
problem. A decision problem is defined as any problem that given an input can
determine or *decide* with "yes" or "no" answer. For example, given a path and a
budget cost as inputs, the decision problem might output "yes" if the path cost
is equal to or lower than the budget cost. Likewise, the decision problem might output "no" if the path cost is higher than the budget cost.

To be more precise, P problems are a set of decision problems that can be solved in polynomial
time *and* verified in polynomial time. For the decision problem used as an
example above, our verification algorithm may sum up the cost of edges in linear time ( O(n) ) to
compare it with the budget cost while the search algorithms such as DFS/BFS
obtain the path in linear time as wel. On the other hand, NP problems are
a set of decision problems which can be verified in polynomial time, but *not
necessarily* solved in polynomial time.

Although a common misunderstanding is to
conceptualize NP as "*not* P", such notion is greatly misleading. Note that NP
problems may or may not be solved in polynomial time. Therefore, NP and P are
not mutually exclusive classes. Rather, P is a subset of NP; all P problems
automatically qualify as NP problems since all P problems satisfy
polynomial-time verification *as well as* polynomial-time solution, and since NP
problems only need to fulfill polynomial-time verification, all P problems are NP problems as well.

For more technical details between P and NP, refer to the extra note.

# P versus NP

Now we can tackle P vs. NP problem. The question simiply asks if P equals to NP
or not. In other words, the problem asks, if a
problem can be verified in a polynomial time, can the problem be solved in
a polynomial time *all the time*? That is, are some NP problems inherently
difficult or even impossible to solve in polynomial time, or have we just
not found the fast algorithms *yet*? So far, no official proof has been
recognized by the Clay Mathematics Institute, which promises to reward
one million dollars to anyone who can solve the P vs. NP problem. Although the question is simple, the implication is significant.

# Implications of P = NP

If P = NP is proven, then this implies that all problems that can be verified in polynomial time can also be solved in polynomial time as well. The impact extends beyond the academic world since many industrial algorithms including cryptography are written under the assumption that P != NP.

For example, RSA, which is a widely used cryptosystem to secure data transmission, exploits P != NP by designing a decryption algorithm that runs in polynomial time only for those who have the right access (known as a private key). If you do not have the private key (meaning you do not have access), you would need to solve the RSA problem, which is a NP problem since there is no known algorithm that can decrypt encryption in polynomial time.

However, if P = NP is proven true, this implies that there exists some algorithms that can solve the RSA problem in polynomial time, meaning any encrypted message can be decrypted easily by even those who should not have access if they can find the polynomial-time decryption algorithm, which is not supposed to exist under the P != NP assumption.

Obviously, this is a significant security threat since this "encrpyted message" could be a private message that you may not wish to share or even financial information that can be hijacked.

**Therefore, if P = NP is true, many of the current algorithms that assume P !=
NP become insecure or invalid, and people can maliciously exploit the algorithm
for their personal gains.**

# Implications of P != NP

If P != NP is true, there are some NP problems that will never be transition into P, meaning there never will be algorithms that can solve those NP problems in polynomial time.

Although the impact of this proof will not be as significant as P = NP since most of the the academia and the industry already assume P != NP, the proof will influence how
researchers spend their time. **Since there cannot be a
polynomial-time solution for some NP problems, researchers would no longer have
to waste their time trying to find fast algorithms for problems in NP.**

# Extra Note

NP stands for "non-deterministic polynomial time" and although P does not have an official abbreviation, it is commonly known as "deterministic polynomial time". A non-deterministic polynomial problem can be solved in polynomial time with some lucky guesses. For example, finding a least-cost cycle that visits every node in a graph is known as a Travelling Salesman Problem, which is notoriously difficult. However, if our solution algorithm makes certain smart/lucky decisions in finding the path, the optimal path could be found in polynomial time.

Meanwhile, the P problem can find a solution in polynomial time without depending on luck. As mentioned before, since P is in NP under P != NP, P problems can also find polynomial-time solution with some lucky guesses.

Click to read and post comments