Large Language Model for Science: A Study on P vs. NP
Authors: name: Qingxiu Dong; name: Li Dong; name: Ke Xu; name: Guangyan Zhou; name: Yaru Hao; name: Zhifang Sui; name: Furu Wei
Published: 2023-09-11 17:49:27

Abstract: In this work, we use large language models (LLMs) to augment and accelerate
research on the P versus NP problem, one of the most important open problems in
theoretical computer science and mathematics. Specifically, we propose Socratic
reasoning, a general framework that promotes in-depth thinking with LLMs for
complex problem-solving. Socratic reasoning encourages LLMs to recursively
discover, solve, and integrate problems while facilitating self-evaluation and
refinement. Our pilot study on the P vs. NP problem shows that GPT-4
successfully produces a proof schema and engages in rigorous reasoning
throughout 97 dialogue turns, concluding "P neq NP", which is in alignment
with (Xu and Zhou, 2023). The investigation uncovers novel insights within the
extensive solution space of LLMs, shedding light on LLM for Science.