Curing cancer is as hard as a Sodoku problem (or God’s Catch 22).
The curse of P != NP.
If you sit me down to talk and we get to talking about Cancer, Democracy, Poverty and other such topics, that neither of us are experts about, I am sure we would throw around words like “Capitalism”, we’d discuss Universal Healthcare, We’d blame pharma — A bunch of banal discussions. I do not know the first thing about Protein foldings, you do not know the first thing about Healthcare. But we are both are aware of one basic facet of problem solving: All big problems are a sum of smaller ones. My rather insenitive and sensationalist headlines may have been a little offensive, and they are incorrect. Cobham’s thesis states that any computational problem can be feasibly computed on some computational device only if they can be computed in Polynomial Time. P-time problems does not mean that the problem is easy, so if we somehow derive that P == NP, it does not mean overnight we could find a cure for cancer, input data does affect the computation time. Donald Knuth put it best
“I don’t believe that the equality P = NP will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive.”
What is P vs NP?
P versus NP is one of the biggest unsolved problems in Computer Science. The premise of this problem is simple: If a problem’s solution can be verified rather quickly, does it also mean we can solve it rather quickly?
Of course, quickly does not refer to the word quickly as you would colloquially use, here the word “quickly” has a special connotation. It means that a problem is solvable in polynomial time, such that the time required is a polynomially dependent on the input size. Take something as simple as Mulitplication for example, one of the simplest P-problems. Now I cannot run a multiplication for infinitely increasing input data on my device and benchmark it, but if I did, it would yield the graph of a Polynomial Function. P-class programs are all programs you know you can solve in Polynomial Time.
NP-class problems are easier to explain. The entire set of NP-class problems consists of decision problems where if the answer to the decision problem is “Yes”, we can verify it in a polynomial time. NP means Non-Deterministic Polynomial. Nondeterminism refers to the fact that certain algorithms behave differently depending on the input, they do not yield a Polynomial graph consistently. Any probablistic algorithm that is dependent on a True Random Number Generator can not be predictable: It can behave polynomially or exponentially.
Now there are a ton of decision problems subclasses that are under NP-class. For example, the NP-complete problems. NP-complete problems are the essence of NP-class problems, and we will discuss one of the problems that best encapsulates the NP-complete problem class: Boolean Satisfiability Problem (or SAT). SATs present a very unique problem: It says given a boolean formula, are there certain inputs we can give for the boolean formula to yield a true value. Keep in mind, the problem itself requires you to say “Yes” or “No” — Will the boolean expression be satisfied?
If I give you a circuit with an AND gate, OR gate and a NOT gate, and configure it in some way, and ask you are there some inputs that can lead to the answer “TRUE”, you would use intuition and experience if you have done these problem problems before. But if you have not, you would use Brute Force, you would write the table and calculate the answer for all possible entries. Best case, you can solve it in a time related to the input polynomially, worst case: Exponentially. It is impossible to determine how much time you will take, especially if I ramp up the number of gates. But if I ask you, can X and Y be multiplied, both being a specific types of compatible numbers, you can give the answer pretty quickly, and we know that you will be quick even if I ramp up the number of multiplicands. The first problem is NP-complete, the second is a P-class problem.
Now you are not a computer, and this analogy was not scientific. I wouldn’t be surprised if I am shunned by academia because of this (Just kidding, Computer Science is rather welcoming). Because you are not a computer. You are very different from a computer. In Industry, these Boolean Expressions have millions of clauses, we can’t brute force our way through everything. For this we have SAT solvers — These try to use clever tricks to find the answer to Boolean Satisfiability Problem (Example Davis-Putnam-Logemann-Loveland algorithm, although we have come a long way from that). But despite that, time for formulating an answer is undetermined — As I said, NP does not mean slow, and P does not mean fast.
What would happen if P = NP
[OPINION]
There is general consensus in academia that P != NP. I believe that in Science, Consensus of academics should not matter. But this topic is where I am in the gray: It seems so intuitive that P != NP is true, but if we consider P != NP as the final answer, we would never strive to prove otherwise. If we manage to prove P = NP, public key cryptography would be broken. Encryption systems would struggle to survive, Bitcoin would be dead. But if we can find that P = NP, we can use these the forumulation to break down NP-class problems into P-class problems. We can find out how to fold a Protein to save someone from cancer, we can enhance our industries, AI et al.. But that is wishful thinking, that should happen, doesn’t mean it will happen. Knuth says these proofs would be nonconstructuve: It would provide the axiom P = NP, without providing an example. It would take years to build on it. The irony is that proving P = NP is True is an NP-class problem by itself, since all methods in a proof are a clause of some form. You should definitely not be holding your breath about someone proving P = NP, go back to your IDEs and start optimizing your codes 😁.
🌺 Hey, hope you enjoyed reading that article. I am Abhinav, editor @ The Crypto Element. It takes a lot of work to research for and write such an article, and a clap or a follow 👏 from you means the entire world 🌍 to me. It takes less than 10 seconds for you, and it helps me with reach! You can also ask me any questions, or point out anything, or just drop a “Hey” 👇 down there. I 💓 making new friends!
