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

ZDNet calls it "a deep meditation on what can ultimately be achieved with computers" and "the single most important unsolved problem in computer science," with implications for both cryptography and quantum computing. "The question: Does P = NP?" "Now, that effort has enlisted the help of generative AI."In a paper titled "Large Language Model for Science: A Study on P vs. NP," lead author Qingxiu Dong and colleagues program OpenAI's GPT-4 large language model using what they call a Socratic Method, several turns of chat via prompt with GPT-4. (The paper was posted this month on the arXiv pre-print server by scientists at Microsoft, Peking University, Beihang University in Beijing, and Beijing Technology and Business University.) The team's method amounts to taking arguments from a prior paper and spoon-feeding them to GPT-4 to prompt useful responses. Dong and team observe that GPT-4 demonstrates arguments to conclude that P does not, in fact, equal NP. And they claim that the work shows that large language models can do more than spit back vast quantities of text, they can also "discover novel insights" that may lead to "scientific discoveries," a prospect they christen "LLMs for Science...." Through 97 prompt rounds, the authors coax GPT-4 with a variety of requests that get into the nitty-gritty of the mathematics of P = NP, prepending each of their prompts with a leading statement to condition GPT-4, such as, "You are a wise philosopher," "You are a mathematician skilled in probability theory" - in other words, the now familiar game of getting GPT-4 to play a role, or, "persona" to stylize its text generation. Their strategy is to induce GPT-4 to prove that P does not, in fact, equal NP, by first assuming that it does with an example and then finding a way that the example falls apart - an approach known as proof by contradiction... [T]he authors argue that their dialogue in prompts shows the prospect for large language models to do more than merely mimic human textual creations. "Our investigation highlights the potential capability of GPT-4 to collaborate with humans in exploring exceptionally complex and expert-level problems," they write.

Read more of this story at Slashdot.