GPT-4 explores global problems through 97 rounds of dialogue and reaches the conclusion that P≠NP

For those who are in the field of scientific research, they have more or less heard of the P/NP problem. This problem was included in the Millennium Prize problem by the Clay Mathematics Institute. There are seven problems in it. Big problems, including the well-known Poincaré conjecture, Riemann hypothesis, etc. And the organization has offered millions of dollars in prizes to researchers who can solve the problem.

The P/NP problem was first proposed in 1971 by Stephen A. Cook and Leonid Levin respectively. Over the years, many people have devoted themselves to researching this problem. However, some people say that it may take a conservative estimate of 100 years to solve the P=NP problem

In recent years, some people have claimed to have proved that P is equal to or not equal to NP, but these There are errors in the proof process. However, so far, no one has been able to give a definite answer

With the development of artificial intelligence technology, especially the rapid update of large language models in the past year, researchers Begin to try to use artificial intelligence technology to solve some global problems

Researchers from Microsoft Research, Peking University, Beihang University and other institutions proposed to use large language models (LLM) to enhance and accelerating the research on P versus NP problems

This article proposes a general framework, Socratic reasoning, to prompt LLM to think deeply and solve complex problems. On the basis of this framework, LLM is able to recursively discover, solve and integrate problems, while also conducting self-evaluation and improvement

This paper's pilot study on the P vs. NP problem shows that, GPT-4 successfully generated a proof pattern and conducted rigorous reasoning in 97 dialogue rounds, reaching the conclusion that "P≠ NP", which is consistent with the conclusion of (Xu and Zhou, 2023).

Please click the following link to view the paper: https://arxiv.org/pdf/2309.05689.pdf

The main contributions of this article can be summarized as follows:

• ## Use LLM as a collaborative partner with humans to address complex scientific challenges, and propose "LLM for Science (LLM4Science )" paradigm.
• Introduces a framework called "Socratic Reasoning" to encourage LLM to use deduction, transformation, decomposition and other modes to stimulate critical thinking.
• Conduct a pilot study using GPT-4 and the Socratic reasoning framework to solve P versus NP problems in theoretical computer science.
• GPT-4 successfully generated proof patterns and conducted rigorous reasoning in 97 dialogue turns, reaching the conclusion that P ≠ NP, consistent with Xu and Zhou (2023 ) recent work consistent.
• This research demonstrates the potential ability of LLMs like GPT-4 to infer new knowledge and explore complex expert-level problems in collaboration with humans.
• This article highlights LLM as a general innovation leader across domains, unlike previous specialized AI models tailored for specific tasks.
• LLM The ability to use natural and mathematical language fluently is essential for interdisciplinary discovery.
• This work reveals how LLM can be leveraged as a partner to enhance and accelerate the scientific research process across diverse fields.

Rewritten content: This paragraph mentions that they named the framework "Socratic Reasoning" after being inspired by the ancient Greek philosopher Socrates. . Socrates once said: "I can teach no one anything. I can only make them think." And the overall design idea of ​​the framework is the same. It is a general problem-solving framework that allows LLM to be used in a wide range of Navigate the solution space and arrive at answers effectively

Table 1 lists the five prompt modes of "Socratic Reasoning": deduction, transformation, decomposition, verification and fusion. These patterns are used to discover new insights and perspectives, break complex problems into sub-questions or small steps, and engage in self-improvement by challenging responses to answers

in smaller problems ( atomic problem), LLM can directly give inference results. At this time, the deductive mode (for example, the prompt is let us think step by step...) is used to guide LLM to directly draw conclusions.

For more complex problems, this article first requires LLM to transform the problem into a new problem or decompose it into several sub-problems. These patterns are then executed recursively until the atomic ji problem is reached.

When new problems arise or new conclusions are drawn, verification mode should be adopted and LLM’s self-assessment capabilities should be used to verify and improve

Finally, the fusion mode requires the LLM to synthesize conclusions based on the results of the sub-problems

recursively motivates the LLM through a series of dialogues to continue the above process until the target problem is solved

In this work, "Socratic Reasoning" provides a systematic prompt framework for challenging questions

The picture below is an example of a dialogue used to solve the P vs. NP problem in "Socratic Reasoning". The GPT-4 API is used in the case study, and in addition, the article sorts the processes based on round index.

In the process of exploration, this article introduces five different roles as auxiliary provers, such as mathematicians who are proficient in probability theory. A total of 97 rounds of dialogue were conducted in the experiment, divided into 14 rounds before and 83 rounds after.

For example, the first round prompt: You can talk from a philosophical perspective rather than from a computer theory From the perspective of P!=NP, can we find the fundamental problem behind P!=NP?

Here are other tips:

The dialogue continues, and the final round of dialogue is as follows: Finally, it is concluded that P≠ NP

Interested readers can Check out the original paper to learn more.

The above is the detailed content of GPT-4 explores global problems through 97 rounds of dialogue and reaches the conclusion that P≠NP. For more information, please follow other related articles on the PHP Chinese website!