Home Tech News Can Generative AI Solve Computer Science’s Greatest Unsolved Problem?

Can Generative AI Solve Computer Science’s Greatest Unsolved Problem?

by Norman Scott

The P vs. NP problem is widely known as one of the most important unsolved problems in computer science, having implications for both cryptography and quantum computing. It has been a topic of intense research and debate for decades. Now, a team of researchers has enlisted the help of generative AI in an attempt to tackle this problem.

In a recent paper titled “Large Language Model for Science: A Study on P vs. NP,” scientists from Microsoft, Peking University, Beihang University, and Beijing Technology and Business University used OpenAI’s GPT-4, a large language model, to gain new insights into the P vs. NP problem. Lead author Qingxiu Dong and his colleagues programmed GPT-4 using a Socratic Method, engaging in several rounds of chat via prompt to elicit useful responses.

The authors observed that GPT-4 presented arguments suggesting that P does not equal NP. This is a significant finding, as it challenges the prevailing belief that the two complexity classes are equivalent. Moreover, the researchers argue that this work demonstrates that large language models like GPT-4 have the potential to “discover novel insights” and contribute to scientific discoveries, a concept they refer to as “LLMs for Science.”

The research team conducted 97 prompt rounds, delving into the mathematics of the P vs. NP problem. They conditioned GPT-4’s responses by prefacing each prompt with leading statements such as “You are a wise philosopher” or “You are a mathematician skilled in probability theory.” This approach aimed to induce GPT-4 to prove that P does not equal NP by assuming it does and then finding a contradiction, known as proof by contradiction.

The authors highlight the significance of their findings, suggesting that large language models can play a collaborative role with humans in tackling complex and expert-level problems. They assert that GPT-4’s ability to provide insights and engage in dialogue goes beyond merely mimicking human text generation. This opens up new possibilities for using AI in scientific research and problem-solving.

The P vs. NP problem remains unsolved, but this study demonstrates the potential of generative AI to contribute to its resolution. By leveraging large language models like GPT-4, researchers can explore complex problems and gain new perspectives. The collaboration between AI and human researchers may pave the way for groundbreaking advancements in computer science and other fields.

You may also like