Skip to content
  1. CLRS-Lean
  2. Chapter 34. NP-Completeness
  3. 34.5. NP-Complete Problems
  4. 34.5. Decision traveling-salesperson problem
  5. 34.5. HAM-CYCLE to TSP reduction machine
  6. 34.5. Vertex Tokens
  7. 34.5. Runtime
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_5_NP_Complete_Problems.TravelingSalesperson.ReductionMachine.VertexTokens.Basic

Fixed vertex-token extractor

noncomputable sectionnamespace CLRS.Chapter34.Turing.TSPReduction.VertexTokensopen PolyBuilderopen _root_.Turingprivate noncomputable def streamComputableInPolyTime : TM2ComputableInPolyTime id id stream := by change TM2ComputableInPolyTime id id (fun input : List CliqueSym => input.flatMap body.emit) exact boundedLoop_computableInPolyTime bodynoncomputable def computableInPolyTime : TM2ComputableInPolyTime encodeCliqueCertificate id tokens := by let raw := streamComputableInPolyTime exact { tm := raw.tm inputAlphabet := raw.inputAlphabet outputAlphabet := raw.outputAlphabet time := raw.time outputsFun := fun vertices => by have output := raw.outputsFun (encodeCliqueCertificate vertices) simpa [stream_encodeCliqueCertificate] using output }end CLRS.Chapter34.Turing.TSPReduction.VertexTokens