Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

NP is closed under polynomial-time many-one reductions

Open
CookPvsNP.mem_NP_of_polyReducible

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexitynp-conp

Let Σ1,Σ2\Sigma_1,\Sigma_2Σ1​,Σ2​ be finite alphabets and let L1⊆Σ1∗L_1\subseteq\Sigma_1^*L1​⊆Σ1∗​, L2⊆Σ2∗L_2\subseteq\Sigma_2^*L2​⊆Σ2∗​ be languages. If L1≤pL2L_1\le_p L_2L1​≤p​L2​ (polynomial-time many-one reducibility, Cook's Definition 3) and L2∈NPL_2\in\mathrm{NP}L2​∈NP, then

L1∈NP.L_1\in\mathrm{NP}.L1​∈NP.

This is the standard closure of NP under polynomial-time reductions. Applied to complements (a reduction fff from L1L_1L1​ to L2L_2L2​ is also a reduction from L1cL_1^{c}L1c​ to L2cL_2^{c}L2c​) it shows that co-NP is closed under polynomial-time reductions as well; for instance, if an NP-complete language lies in co-NP then NP === co-NP.

Formalization Note P, NP and ≤p\le_p≤p​ are those of the Cook problem description (one-tape Turing machines, time bound ∣w∣k+k|w|^k+k∣w∣k+k, checking relations with certificates of length at most ∣w∣k|w|^k∣w∣k).

Preamble
import Mathlib
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace CookPvsNP

theorem mem_NP_of_polyReducible {Sym₁ Sym₂ : Type} [Fintype Sym₁] [Fintype Sym₂]
    (L₁ : Lang Sym₁) (L₂ : Lang Sym₂) (hred : PolyReducible L₁ L₂) (h₂ : L₂ ∈ NP Sym₂) :
    L₁ ∈ NP Sym₁ := by sorry

end CookPvsNP
Source
S. Cook, The P versus NP problem (Clay Mathematics Institute problem description), §2, remarks after Definition 4 (closure of NP under ≤p); used in Karp & Papadimitriou, MIT/LCS/TM-154 (1980), p. 8, proof of Corollary 1

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me