A computer science conundrum that could transform healthcare

The P vs NP question is a problem in mathematics and computer science, but that does not mean it will be confined there

Updated - May 03, 2024 10:42 am IST

Published - May 03, 2024 05:30 am IST

Medical equipment on the background of group of health workers in the ICU. Representative image.

Medical equipment on the background of group of health workers in the ICU. Representative image. | Photo Credit: Getty Images/iStockphoto

In 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 field of microbiology. It offered solutions to challenges in healthcare that until then had seemed intractable.

(For top health news of the day, subscribe to our newsletter Health Matters)

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.

P 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 fields 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 filled with complex problems. 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 — staff 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 find the optimal solution to these scheduling problems, thus significantly 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 confined 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 significant 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 effective 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 Bharath can contribute more effectively to achieving universal health coverage.

By solving these complex problems more efficiently, 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 difficult 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 beneficiary of this problem-solving. The barrier that the P vs NP problem stands for encompasses every field where the solution to a problem is blocked by the availability of significant computational resources. So these fields include logistics, finance, 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 offer a million dollars to anyone who can definitively 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 redefine 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.)

0 / 0
Sign in to unlock member-only benefits!
  • Access 10 free stories every month
  • Save stories to read later
  • Access to comment on every story
  • Sign-up/manage your newsletter subscriptions with a single click
  • Get notified by email for early access to discounts & offers on our products
Sign in


Comments have to be in English, and in full sentences. They cannot be abusive or personal. Please abide by our community guidelines for posting your comments.

We have migrated to a new commenting platform. If you are already a registered user of The Hindu and logged in, you may continue to engage with our articles. If you do not have an account please register and login to post comments. Users can access their older comments by logging into their accounts on Vuukle.