Polynomial binary program preimages preserve native multistack NP
ProvedPvsNP.np_preimage_polyprogramalgorithmsclusteringcomputational-complexity
Precompose any NP language with a polynomial binary program and construct a checker in PvsNP.NP. Witnesses are clipped to the simulated bound, and the three inputs of length at most one are handled within the native pure-power certificate convention.
Preamble
import Definitions.Def_PvsNP import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem PvsNP.np_preimage_polyprogram (L : Language Bool) (hL : L ∈ PvsNP.NP)
(g : List Bool → List Bool) (hg : Poly g) :
({w | g w ∈ L} : Language Bool) ∈ PvsNP.NP := by
sorry
Source
Stephen Cook, The P versus NP Problem, verification definition of NP. The Prove2Me PvsNP and finite binary-verifier encodings. Polynomial many-one inverse images of NP languages are in NP.