NP-Complete problems 2

Showcasing reductions between these NP-complete problems:

• 3SAT ≤_p HCYCLE
• HCYCLE ≤_p HCIRCUIT
• HCIRCUIT ≤_p TSP
• 3SAT ≤_p SSP
• 3SAT ≤_p 3DM
• 3DM ≤_p SSP

Notes

As far as I know, there is no concrete/correct way to differentiate between "hamiltonovsky cyklus" and "hamiltonovska kruznice" in the English language. In this project I chose this naming:

• HCYCLE - here means "hamiltonovsky cyklus"
• HCIRCUIT - here means "hamiltonovska kruznice"

HCYCLE is asking wether there is a hamiltonian cycle in a directed graph. HCIRCUIT is asking wether there is a hamiltonian cycle in an undirected graph.