Skip to content
  1. CLRS-Lean
  2. Chapter 34. NP-Completeness
  3. 34.5. NP-Complete Problems
  4. 34.5. HAM-CYCLE
  5. 34.5. Fixed VERTEX-COVER to HAM-CYCLE reduction machinery
  6. 34.5. Public fixed VERTEX-COVER to HAM-CYCLE reduction machine
Browse chapters
Imports
import CLRSLean.Chapter_34.Section_34_5_NP_Complete_Problems.HamiltonianCycle.ReductionMachine.RawTotal.Runtime

Public fixed VERTEX-COVER to HAM-CYCLE reduction machine

noncomputable sectionnamespace CLRS.Chapter34.Turing.HamiltonianCycle.ReductionMachineopen _root_.Turing

A fixed polynomial-time TM2 computes the all-input guarded HAM-CYCLE reduction map from raw VERTEX-COVER words.

noncomputable def computableInPolyTime : TM2ComputableInPolyTime id id RawTotal.machineVertexCoverToHamiltonianMap := RawTotal.computableInPolyTime
end CLRS.Chapter34.Turing.HamiltonianCycle.ReductionMachine