Polynomial-time functions admit tagged pairing on a shared input
ProvedCookPvsNP.polyTimeComputable_tagged_pairLet and be polynomial-time functions on words over finite alphabets. Write for a tagged copy of , a fresh separator, and a tagged copy of . Then the function
is polynomial-time computable on a deterministic one-tape Turing machine. The same input supplies both computations. This closure property is used to implement the answer map in the composition of Levin reductions.
Preamble
import Definitions.Def_CookPvsNP_defs
Formal statement
namespace CookPvsNP
theorem polyTimeComputable_tagged_pair {A B C : Type} [Fintype A] [Fintype B] [Fintype C]
(f : List A → List B) (g : List A → List C)
(hf : PolyTimeComputable f) (hg : PolyTimeComputable g) :
PolyTimeComputable (fun x => (f x).map (some ∘ Sum.inl) ++ none :: (g x).map (some ∘ Sum.inr)) := by sorry
end CookPvsNP
Source
Cook, The P versus NP Problem, Appendix (one-tape Turing machine model), https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf . Standard closure construction for the tagged pairing used in polynomial-time search reductions.