Can generative AI solve computer science's greatest unsolved problem?

Computer scientists contemplate whether the time required to compute a solution is out of reach for the hardest problems. The question of Does P = NP? is now treated as a multi-prompt session with the GPT-4 language model. The greatest insight of the work may be how to prune past chat sessions to maintain a discussion.

artpartner-images/Getty Images

When computer scientists hang out at cocktail parties, they're apt to chat, among other things, about the single most important unsolved problem in computer science: the question, Does P = NP? 

Formulated nearly 50 years ago, the question of whether P equals NP is a deep meditation on what can ultimately be achieved with computers. The question, which has implications for fields such as cryptography and quantum computing, has resisted a convincing answer despite decades of intense study. Now, that effort has enlisted the help of generative AI.

AI in 2023: A year of breakthroughs that left no human thing unchanged These are the jobs most likely to be taken over by AI AI at the edge: 5G and the Internet of Things see fast times ahead Almost half of tech executives say their organizations aren't ready for AI or other advanced initiatives AI in 2023: A year of breakthroughs that left no human thing unchanged

These are the jobs most likely to be taken over by AI

AI at the edge: 5G and the Internet of Things see fast times ahead

Almost half of tech executives say their organizations aren't ready for AI or other advanced initiatives

Editorial standards Show Comments