A computer science conundrum that could transform healthcare

While it may sound like a cryptic puzzle reserved for computer science mavens, the implications of the P versus NP problem stretch beyond algorithms and data structures, rippling through diverse elds, including antimicrobial resistance, cancer care, and m

n the 17th century, a Dutch draper named Anton van Leeuwenhoek used a small handmade microscope to peer into a world previously unseen by the human eye. Thus he discovered microorganisms and gave rise to the —eld of microbiology. It oered solutions to challenges in healthcare that until then had seemed intractable.

Today, we face a new set of complex problems in healthcare that seem more intractable than others before for their inherent complexity and the constraints they threaten to impose on resources.

IP versus NP

It so happens that an unsolved problem in computer science, simply called the P versus NP problem, could hold the key to these modern-day conundra. While it may sound like a cryptic puzzle reserved for computer science mavens, its implications stretch beyond algorithms and data structures, rippling through diverse —elds including healthcare. But what exactly is this puzzle, and how could its resolution unlock a new era in medical science?

Let’s start with a simple arithmetic example. Say you’re asked to multiply 17 with 19. With some time, you’d arrive at the answer: 323. This is a ‘P’ problem: you can solve it reasonably quickly. (‘P’ stands for polynomial time.) Suppose you’re presented with 323 and asked to identify the two prime numbers multiplied to get this. In this case, you will have to take the trial and error route until you arrive at 17 and 19. This is an ‘NP’ problem: it takes longer to solve, but once you have the solution, you can verify it quickly. (‘NP’ here is nondeterministic polynomial time.)

Healthcare is —lled with complex issues. Consider scheduling in a hospital: assigning doctors and nurses to shifts, booking operating theatres for surgeries, and organising patient appointments. It is an intricate puzzle that requires considering various factors — sta availability, urgency of medical cases, etc. — and potential changes such as emergency cases and cancellations.

The P vs NP question is this: could there be a shortcut to solve ‘NP’ problems as quickly as ‘P’ problems? Because the implication is that if P equals NP, we could quickly —nd the optimal solution to these scheduling problems, thus signi—cantly improving patient care.

The implications of resolving this question are profound and wide-reaching, including for healthcare.

Implications for healthcare

The P vs NP question is a problem in mathematics and computer science, but that does not mean it will be con—ned there. If an existing problem can be given a faithful mathematical representation and is found to be an ‘NP’ problem, the shortcut in question could help by turning it into a ‘P’ problem.

For example, antibiotic resistance is a signi—cant global health concern. If P equals NP, we may have a way to quickly analyse bacterial genomes and predict their resistance patterns, helping doctors prescribe the most eective antibiotics. This would improve patient outcomes and help combat antibiotic resistance, including new antibiotics discoveries for emerging diseases. Of course, patients’ adherence will still matter.

Cancer is a complex disease with myriad mutations. Deciding the best treatment plan is an NP problem because it involves considering all possible combinations of drugs and therapies. If P equals NP, we may have an opportunity to swiftly identify the optimal treatment for each individual cancer patient and potentially save many lives. The catch here is that we will still need a large volume of data.

Insurance companies grapple with NP problems when they have to determine premiums and packages based on considering numerous variables like age, health status, lifestyle, and medical history. Having a shortcut to crack the P vs NP problem could help these companies optimise their decision-making and pave the way to fairer and more accurate premiums and conditions. Further, government spending on healthcare can also be utilised with minimal leakage while programmes like Ayushman Bharat can contribute more eectively to achieving universal health coverage.

By solving these complex problems more e‘ciently, we could potentially dramatically reduce resource constraints and improve health outcomes.

Surprising sources of progress

While the P vs NP problem is a topic of ongoing study in computer science, the consensus among most experts is that P probably does not equal NP, implying that some problems will remain very di‘cult to crack, even if a solution — once it is found — will be easier to verify. But this has not deterred researchers from exploring this question, and in the pursuit of which they have unearthed improvements to algorithms and new approaches to dealing with complex problems.

Throughout history, there have been many instances of seemingly insurmountable problems being overcome with innovative thinking.

Before the discovery of electricity, for example, candlemakers lit our world. Yet most of them may never have foreseen the revolutionary consequences of Thomas Edison’s incandescent bulb, which brought light to more people and for longer hours.

Similarly, following the invention of calculus and expanding the binomial theorem to negative integers and fractions, Isaac Newton considerably improved our understanding of the irrational number pi. Why, the technology giant Apple has been transforming our expectations of what a watch can be expected to do in ways that Swiss watchmakers may never have anticipated.

Not all will be winners

This said, one potential drawback of P being equal to NP, if ever that outcome comes to pass, lies in the realm of cryptography. Many encryption schemes and algorithms rely on problems that are currently hard to solve, believed to be in the set of ‘NP’, not ‘P’ problems. That is, these schemes protect secrets by hiding them behind a problem that is very hard to solve but easy to verify. If P equals NP, these problems will become easy to solve, rendering these encryption schemes vulnerable to attacks and compromising digital security.

This said, healthcare isn’t the sole bene—ciary of this problem-solving. The barrier that the P vs NP problem stands for encompasses every —eld where the solution to a problem is blocked by the availability of signi—cant computational resources. So these —elds include logistics, —nance, and even climate modelling, all of which could experience paradigm shifts if the P vs NP problem is solved in favour of the P = NP outcome.

The Clay Mathematics Institute in Colorado continues to oer a million dollars to anyone who can de—nitively solve the P vs NP problem. But for anyone who does, a million dollars will pale in comparison to the rewards they stand to collect by revolutionising various human enterprises, potentially driving human progress in unimaginable ways.

As we look to the future, let us remember that problems that seem insurmountable today might not be so tomorrow. As with the candlemakers, the watchmakers, and even Anton van Leeuwenhoek, the solution often comes from where we least expect it. Today’s brightest minds grappling with the P vs NP problem may be on the brink of a breakthrough that could rede—ne healthcare as we know it.

(Dr C. Aravinda is a public health physician and student at IIT Madras pursuing a BS degree in data science.)

If P equals NP, we may have a way to quickly analyse bacterial genomes and predict their resistance patterns, helping doctors prescribe the most eective antibiotics. This would improve patient outcomes and combat antibiotic resistance

GETTY IMAGES/ISTOCKPHOTO Healthcare is filled with complex issues like assigning doctors and nurses to shifts, booking operating theatres for surgeries, and organising patient appointments.