# Large Language Model for Science: A Study on P vs. NP

arXiv: https://arxiv.org/abs/2309.05689 · HTML: https://mlsanity.com/paper/2309.05689/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 13 references that are in the map.
- First posted on arXiv 11 Sep 2023.

## Builds on (most cited first, 5 of 5)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)

## Built on by (most cited first, 12 of 12)

- [MathVista: Evaluating Mathematical Reasoning of Foundation Models in Visual Contexts](https://mlsanity.com/paper/2310.02255/) (2023)
- [Exploring Large Language Model based Intelligent Agents: Definitions, Methods, and Prospects](https://mlsanity.com/paper/2401.03428/) (2024)
- [OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling](https://mlsanity.com/paper/2407.09887/) (2024)
- [SocREval: Large Language Models with the Socratic Method for Reference-Free Reasoning Evaluation](https://mlsanity.com/paper/2310.00074/) (2023)
- [Polymath: A Challenging Multi-modal Mathematical Reasoning Benchmark](https://mlsanity.com/paper/2410.14702/) (2024)
- [Triad: A Framework Leveraging a Multi-Role LLM-based Agent to Solve Knowledge Base Question Answering](https://mlsanity.com/paper/2402.14320/) (2024)
- [A Survey of Large Language Models on Generative Graph Analytics: Query, Learning, and Applications](https://mlsanity.com/paper/2404.14809/) (2024)
- [Mitigating Tail Narrowing in LLM Self-Improvement via Socratic-Guided Sampling](https://mlsanity.com/paper/2411.00750/) (2024)
- [Socratic-PRMBench: Benchmarking Process Reward Models with Systematic Reasoning Patterns](https://mlsanity.com/paper/2505.23474/) (2025)
- [RICo: Refined In-Context Contribution for Automatic Instruction-Tuning Data Selection](https://mlsanity.com/paper/2505.05327/) (2025)
- [Lost in Translation: Latent Concept Misalignment in Text-to-Image Diffusion Models](https://mlsanity.com/paper/2408.00230/) (2024)
- [Smotrom tvoja pa ander drogoj verden! Resurrecting Dead Pidgin with Generative Models: Russenorsk Case Study](https://mlsanity.com/paper/2506.11065/) (2025)

## Abstract (arXiv)

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.