Day: July 3, 2019

You may have heard of the famous P versus NP problem. If you can prove or disprove its cryptically short equation, you’d be a million dollars richer—and maybe even billions of dollars richer, depending on your scruples.

The importance of P versus NP is mainly in its consequences for computing. It happens to be one of the seven Millennium Prize Problems, meaning The Clay Mathematics Institute of Cambridge, Massachusetts will award $1 million to whomever manages to prove or disprove the statement. But should you prove that P in fact does equal NP, you wouldn’t even need the $1 million prize. As theoretical computer scientist Scott Aaronson explained last week at a lecture in a stuffy auditorium at Los Alamos National Lab in New Mexico, proving that P=NP would open up some intriguing possibilities.

“If someone proves P=NP, the first thing they should do is steal $200 billion in bitcoin. The second thing they should do is solve all of the other Millennium Prize Problems,” Aaronson said.

To understand this, you need to know that computers are devices that solve problems, abstracted into code readable by the physical computing device, based on the principles put forth by Alan Turing. Solving problems takes a number of steps and a certain amount of time, with the amount of time required increasing as the problem grows larger.

“P” refers to the problems that computers solve all the time, from something as simple as multiplying two numbers to more complex tasks like browsing the internet. As a problem grows in complexity, the amount of time it takes to solve it grows in “polynomial time,” where a polynomial is a number with a power and a coefficient (like n²). If a problem is solvable in n² time and you double the size of the input, then the amount of time it would take to solve would go up by four.

Yet there are plenty of problems where one can determine that a given answer is correct in polynomial time, but actually getting to that answer may or may not be possible in polynomial time. These are called “Nondeterministic Polynomial time” or NP problems. Sudoku is an NP problem—hard to solve, easy to check. Another important example today is factoring large numbers into prime numbers. For now at least, it takes a very long time—slower than polynomial time—to factor very large numbers into primes, but checking that an answer is correct is as simple as multiplying the resulting numbers together. Indeed, this exact idea is the basis of modern encryption, which relies on generating security keys that are easy to verify but hard to crack.

Newer mathematical proofs have found, and might continue to find, P solutions to some of these NP problems. The P versus NP problem asks whether every NP problem has a P solution, or if there exists some NP problem that can absolutely not be solved in P. It seems like it should be obvious that P does not equal NP, but it is not rigorously mathematically proven. And if you happen to prove that P does equal NP, you will have also demonstrated that there are polynomial-time algorithms for a whole lot of very important computer problems. You could make yourself very rich—bitcoin mining and security keys rely on hard-to-solve, easy-to-check NP problems.

Quantum computers, which are based on different mathematics than classical computers, do not promise P solutions to every NP problem. It was once thought that they might be able to solve the hardest class of NP problems, called NP-complete problems. If you could find an efficient solution to those, you’d be able to find efficient solutions to all NP problems. This includes the traveling salesman problem and a host of other similar optimization problems. But quantum computers haven’t lived up to this hype. Instead, quantum computers might solve some P problems in a shorter time (as in, with a lower polynomial) or move some NP problems into the quantum generalization of P, called BQP or “Bounded-Error Quantum Polynomial Time.”

So go out there and try and prove that P does, or does not, equal NP. If you’re successful, you’ll make at least a million dollars, and perhaps much, much more. If you’re unsuccessful, well, hopefully you will have led a meaningful life researching computational theory.

An interdisciplinary team of scientists is claiming to have eliminated the HIV virus from the genomes of mice by combining the CRISPR-Cas9 gene-editing tool with an experimental new drug. It’s a promising development in the battle against HIV and AIDS, but more work is required before clinical trials can begin.

Using a gene-editing tool like CRISPR to clear out an infectious disease may seem strange, but HIV is a retrovirus that embeds itself within DNA as a means to replicate. Antiretroviral therapy, or simply ART, can suppress HIV replication, but it can’t eliminate every trace of the disease, as it’s not capable of purging cells in which the virus has gone dormant.

As new research published in Nature Communications shows, CRISPR-Cas9, when used in conjunction with an exciting new form of ART, provided a one-two punch that flushed out the virus from the genomes of a living animal. That’s never been done before.

In experiments on mice that were genetically modified to have certain similarities with humans, a research team led by Kamel Khalili from the Lewis Katz School of Medicine at Temple University eliminated all traces of the HIV virus in slightly more than 30 percent of infected mice. It’s not a perfect result, but it provides reason to be optimistic.

“We now have a clear path to move ahead to trials in non-human primates and possibly clinical trials in human patients within the year,” said Khalili in a press release.

Khalili, it’s worth pointing out, is the founder and principal scientific advisor of Excision BioTherapeutics, a Philadelphia-based company that uses CRISPR to treat viral diseases. Excision BioTherapeutics holds the exclusive license for the commercial application of this new therapy. Nearly 37 million people worldwide are infected with HIV-1, and more than 5,000 people are infected each day, according to UNAIDS.

So it makes sense that this team is eager to begin clinical trials, but the new research needs to be met with a hefty dose of caution. In addition to explaining the low success rate, the researchers will need to show that the CRISPR edits aren’t resulting in long-term side effects, such as cancer.

Antiretroviral therapy for AIDS changed the lives of millions, but it’s not a cure in the technical sense. Patients have to take medicines on a regular basis to keep the HIV virus in check, lest it re-emerge in the body and proliferate to dangerous levels. What we really need is a therapy that completely eliminates HIV from the body—which is precisely what Khalili and his colleagues have been working on for the past several years.

Previously, Khalili’s team showed that CRISPR could be used to excise HIV DNA from infected genomes. But this approach, like ART, wasn’t able to completely eliminate the virus on its own. For the new study, Khalili recruited the help of Howard Gendelman, a professor of infectious diseases and internal medicine at the University of Nebraska Medical Center.

Gendelman has been working on a new approach to ART called LASER, or long-acting slow-effective release. This system targets cellular reservoirs where the HIV virus hides and is capable of suppressing the replication of the virus for extended periods. To do this, the drug is wrapped in nanocrystals, which help it spread to tissues where HIV is most likely to be dormant. Once at the desired location, the nanocrystals can stay inside the cells for weeks, slowly releasing the drug.

This approach to ART caught the attention of Khalili, who “wanted to see whether LASER ART could suppress HIV replication long enough for CRISPR-Cas9 to completely rid cells of viral DNA,” he said in a release.

In experiments, the researchers used bioengineered mice with human T cells capable of contracting an HIV infection. Using both LASER ART and CRISPR-Cas9, the researchers completely eliminated HIV DNA in about one-third of the infected mice. Tests of blood, bone marrow, and lymphoid tissue—places where HIV likes to hide and go dormant—revealed no traces of the virus. The researchers also didn’t observe any long-term damage to the mice’s cells.

Kevin Morris, a professor at the Centre for Gene Therapy at City of Hope, told Gizmodo that “this is a very exciting paper” and the researchers showed “HIV can be removed from HIV-infected mice.” That said, Morris, who wasn’t affiliated with the new study, was “very, very concerned” about the potential for this CRISPR-based therapy to go off the rails.

“[I]t has the risk of causing cancer,” Morris said. “This is because the approach depends on using a gene therapy that is known to persist a long time in the body. The long-term persistence could lead to CRISPR—which cuts HIV out of the cell—cutting other sites in an uncontrolled manner. The cutting of other sites in the human cell could lead that cell to become cancerous.”

Despite this, Morris said it’s nice to see, at least at the conceptual level, that it’s possible to eliminate the virus from infected mice.

As a final note, the new study involved a multidisciplinary team consisting of virologists, immunologists, molecular biologists, pharmacologists, and pharmaceutical experts. No one said it was going to be easy to find a cure for HIV—but this multifaceted approach offers a glimpse into how it might actually be done.