NP is closed under polynomial-time many-one reductions
OpenCookPvsNP.mem_NP_of_polyReduciblecomputational-complexitynp-conp
Let be finite alphabets and let , be languages. If (polynomial-time many-one reducibility, Cook's Definition 3) and , then
This is the standard closure of NP under polynomial-time reductions. Applied to complements (a reduction from to is also a reduction from to ) 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 are those of the Cook problem description (one-tape Turing machines, time bound , checking relations with certificates of length at most ).
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