The first projection of the pair code is polynomial-time computable
ProvedCookPvsNP.polyTimeComputable_pairFstcomplexity-theory
For finite alphabets and , a pair of words is coded as over , with the separator as in Cook's checking languages. Some polynomial-time computable satisfies
This is the companion of the proved second projection lemma. It lets a search-reduction decoder recover the original instance from the instance–answer pair.
Formalization Note is total and must run in polynomial time on all words; its values on words not of the form are unconstrained.
Preamble
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace CookPvsNP
theorem polyTimeComputable_pairFst (A B : Type) [Fintype A] [Fintype B] :
∃ g : List (Option (A ⊕ B)) → List A, PolyTimeComputable g ∧
∀ (s : List A) (t : List B),
g (s.map (some ∘ Sum.inl) ++ none :: t.map (some ∘ Sum.inr)) = s := by sorry
end CookPvsNP
Source
S. Cook, The P versus NP problem (Clay Mathematics Institute), Section 1, checking relations and the language L_R = {w#y}; companion of CookPvsNP.polyTimeComputable_pairSnd