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:
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!