Kenneth Regan paused at lunch in New York to glance at incoming texts from top international chess officials. A world-renowned “chess detective,” he’s on call to review games with his specialized algorithm that detects cheating.
Chess players cheat by using computers to find the best moves; an algorithm can detect the probability that a move came from a computer rather than a person.
But Regan, who loves chess but also theoretical mathematics and singing in his church choir, put the phone away. He would analyze the chess games later.
Instead, he resumed explaining one of the greatest unsolved conundrums in mathematics: the P versus NP problem, which could explain how complex the universe is. Regan, 65, has made this question his life’s work, in a field of computer science known as complexity theory.
The P versus NP problem asks, Are all problems feasibly solvable by a computer algorithm, or are there some problems so complex they can never be solved? Are solvable P problems the same as seemingly unsolvable NP problems?
The theory has major implications for artificial intelligence, quantum computing, evolution, and questions about the beginnings of the universe. As artificial intelligence models stand to offer the most powerful computing in human history, P versus NP is one way to consider how far computing can go.
In 2000, the Clay Mathematics Institute designated the P versus NP problem as one of seven “Millennium Prize Problems,” with a $1 million reward for the scientist who solved it. To date, no one has, and no one seems close to an answer either.
If P does not equal NP, then some problems are too complex to solve. If a problem is unsolvable by an algorithm, then that means it is not solvable in all the time in the universe. (Quanta Magazine has a helpful explainer video.) If P equals NP, then the solution to any computational problem is solvable within finite time.
Regan thinks that P does not equal NP and some problems are unsolvable by an algorithm. But he can’t prove it yet.
If P does not equal NP, as Regan believes, then scientists might not be able to ensure the large language models behind generative AI tools are giving consistently correct solutions to problems. If P does not equal NP, that could hamper “efforts to avoid hallucinations” from AI, he said. But mathematicians just don’t know.
The P versus NP question can also apply to other scientific questions, like evolution: “If we see a way to do something, we can postulate it and prove it,” he said. That’s a P problem. He continued: “But it’s very difficult for us to be able to make negative conclusions, for instance, that something could not have evolved naturally. The P versus NP impasse is standing over that.”
A chess prodigy as a child in New Jersey, Regan has the kind of preternatural memory that top chess players must have.
Math and chess are a friendly combination, requiring calculating but also theoretical thinking. Notable mathematician Emanuel Lasker, for example, was the dominant world chess champion at the turn of the 20th century. One modern-day list has Regan, an international chess master, as one of the highest-rated chess players among professional mathematicians.
Over his career, Regan developed the algorithm that FIDE, the International Chess Federation, uses for cheating detection, analyzing hundreds of thousands of historic chess games. In 2022, he found himself at the center of evaluating a major chess scandal where the world champion Magnus Carlsen accused an opponent of cheating.
Regan’s algorithm was the subject of discussion on Reddit threads and podcasts. At the time, one of his fellow church choir members peppered him with questions about the case.
He sees his chess work as more than a hobby for a game. The algorithm he worked on there might apply in other fields; the chess work is also math work.
Regan earned his mathematics PhD as a Marshall Scholar at Oxford University, where he was involved with Christian Union.
Regan remembered sharing a train as a grad student in the 1980s with another complexity theory mathematician, Michael Sipser, who was confident that scientists would solve the P versus NP problem. But now, Regan said, “it seems more remote than ever.”
“It’s considered too formidable to take direct aim at,” he said.
For much of his career, Regan has researched and taught computer science at the University of Buffalo. He has a professor’s warmth to talking through any question—and no self-consciousness about going deep into theoretical mathematics in a diner in Manhattan. But he’ll talk about baseball or skiing too, finding crossovers between math and anything else in life.
Regan argues that his love for God, his love for the humanities, and even his love for chess help make him a good mathematician by allowing him to see the world differently. And a theoretical mathematician must find new ways of thinking to take swipes at a problem like P versus NP.
Almost 30 years ago, a dean of the complexity theory field, Donald Knuth, estimated that only 5–10 percent of his computer science colleagues believed in God. Knuth is a Lutheran like Regan.
Regan believes the number of people of faith in the world of science has grown. He knows other Christians in his department. No one has complained about the sermon links on his professor page or his personal notes on N. T. Wright’s Surprised by Hope.
Regan said he sees his faith as holistically connected to his scientific work but not as a tool to prove the existence of God. His Christianity helps him to see his neighbors through the lens of “people first, not scientific advancement first.”
“Making room for God in science, that I very much want to see,” he said. “We need a scientific community with people accustomed to all ways of thinking.”
Regan grew up Catholic but became Lutheran to join his wife’s denomination. He loves Reformer Martin Luther’s theology of the Cross as a way to look at the world, saying that the “theology of glory needs to be continuous with the theology of the Cross.”
This means that Christianity, he thinks, can see some level of continuity between good, beautiful things in the world and ugly, despised things—“not flip sides on a sheet of paper, but like a Möbius strip,” he said, using another math reference.
On his academic page, Regan links to a sermon from Lutheran pastor Mark Bartels about the theology of the Cross, which states,
Through what appeared to be foolishness, in His great wisdom, He saved the world! And, yes, may He work through the weakness in my life, to make me strong! And, ultimately one day He will take us to glory. He will take us to glory! And let us always remember that, in this world, we live under the cross, the cross of Christ!
Regan approaches complexity theory as a mathematician with an affection for the humanities. He peppers his conversation with references to Jacques Derrida and Willy Wonka. He reads widely: Earlier this year, he was going through the notes in Willis Barnstone’s Restored New Testament and Tim Palmer’s Primacy of Doubt, about how uncertainty in mathematics is scientifically valuable.
“A lot of what we call the big questions—‘Is there life after death?’—they have scientific parallels, and I’m interested in the scientific parallels because you can inquire after them,” Regan said.
He loves church music, insects, languages, flowers, and biking with his wife.
“My best work has been cross-pollinating two areas, such as error-correcting codes to improve the running time of a construction in complexity theory or linking between resource bounds of measure theory,” he said.
Conversation with Regan includes terms like polynomial ideal theory and algebraic geometric invariant theory.
At his father’s funeral, Regan began his eulogy talking about parallel universes and string theory—tossing out the question of whether there are resurrected versions of our bodies in parallel universes.
He enjoys asking any question that interests him, like what God’s chess rating would be. The point of that question is that no one knows what a perfect chess rating is, because machines haven’t solved chess.
Being at the center of big chess and science questions, he sees the importance of “scientific communication,” he said.
“Coming out of the COVID pandemic … we have one side that says, ‘Follow the science,’ but is unclear about explaining what that means—and the other side that excoriates that, or says, ‘Do your own research. Don’t trust,’” Regan said.
“People feel that scientists should be able to give crisp, definite answers,” he said. “And that’s just not the case. Science itself is good. The best science is aware of and infused with doubt.”
As a result, the stalemate on the P versus NP problem doesn’t discourage Regan.
“The impasses in the field ought to be the source of a lot of intellectual humility,” he said. “Humility is a requisite of what I call doing science faithfully.”
Further resources on understanding the P versus NP problem
The Golden Ticket: P, NP and the Search for the Impossible by Lance Fortnow
