In plain words: An AI approach breaks a hard problem into smaller questions, solves each, and repeatedly checks and revises its own answers in a long conversation. On P vs. NP it produced a proof outline over 97 turns concluding P ≠ NP, matching a recent argument.
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.
Qingxiu Dong, Li Dong, Ke Xu, Guangyan Zhou, Yaru Hao, Zhifang Sui, Furu Wei
arXiv:2309.05689 · cs.CL, cs.AI · submitted Sep 11, 2023
abstract · pdf · html · 73 pages