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. Weight Fields
  7. 34.5. Runtime
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_5_NP_Complete_Problems.TravelingSalesperson.ReductionMachine.WeightFields.Basic

Fixed polynomial-time formatter for textbook TSP weight fields

noncomputable sectionnamespace CLRS.Chapter34.Turing.TSPReduction.WeightFieldsopen PolyBuilder

One fixed polynomial-time TM2 formats an arbitrary adjacency-answer stream as canonical compact 1/2 TSP fields.

noncomputable def computableInPolyTime : _root_.Turing.TM2ComputableInPolyTime id id stream := by change _root_.Turing.TM2ComputableInPolyTime id id (fun answers : List Bool => answers.flatMap body.emit) exact boundedLoop_computableInPolyTime body
end CLRS.Chapter34.Turing.TSPReduction.WeightFields