<p>A fairly simple reduction goes from Hamiltonian Cycle to the Travelling Salesman Problem (TSP). </p>

<p>The Hamiltonian Cycle problem on instance $G$ asks whether there exists a tour of some unweighted, undirected graph $G$. </p>

<p>TSP on instance $(G,k)$ asks whether there exists a tour in the weighted, complete graph $G$, of length at most $k$.</p>

<p>The reduction is as follows:<br/>
Given the unweighted graph $G$, construct complete weighted graph $G'$ on the same vertices as $G$. Set the weights such that an edge in $G'$ has weight $0$ if the edge was in $G$ and set the weight to $1$ otherwise. The results of the reduction is the TSP instance $(G', 0)$.</p>

<p>Since any tour in $G'$ is of length zero if and only if it is a tour using only the vertices in $G$, it follows that the answer to the instance for TSP is 'yes' if and only if the answer to the instance for Hamiltonian Cycle is 'yes'.</p>

<p>Since this reduction can be computed in polynomial time, this also shows that TSP is NP-hard if Hamiltonian Cycle  is NP-hard. (Both Hamiltonian Cycle and TSP are known to be NP-hard problems)</p>

CC BY-SA 3.0
2017-05-25T19:03:30.010Z
2017-05-25T22:22:24.097Z
2017-05-25T22:22:24.097Z
Discrete lizard
<p>Considering that you teach HS students, many of the reduction examples "off the market" might be conceptually a bit too complex, and can be confusing even for many college students.</p>

<p>I'd suggest that you choose an example between very similar problems, like the (polynomial time) reduction from 4SAT to 3SAT.</p>

<p>So, what are 4SAT and 3SAT? SAT is the <strong>Boolean satisfiability problem</strong>, or, given a Boolean formula phi, we want to decide if there is a solution to the equation phi = true.</p>

<p>These equations are usually written in <em>conjunctive normal form</em>, or a series of conjunctions of disjunctions, like: "(a or b or c) and (c or d)". When each clause has 3 terms, the problem is called 3SAT. When each clause has 4, it's called 4SAT. Now you might get a sense how one could reduce from 4SAT to 3SAT. One possible reduction (which is extremely simple) is described <a href="https://math.stackexchange.com/questions/571618/convert-4-sat-to-3-sat">here</a> on the Math SE. </p>

CC BY-SA 3.0
2017-05-25T19:14:29.313Z
2017-05-25T19:25:46.100Z
2017-05-25T19:25:46.100Z
xuq01
<p>So, I am preparing to teach about P and NP for the first time.  I know that I need to teach about Mapping Reducibility (aka One-to-One Reducibility).  Can anyone recommend a set of algorithms that are easy to use to clearly illustrate the idea?  The algorithms in this first brush with the topic don't, themselves, have to be NP - I just want to show a remapping that is extremely clear in order to impart the concept.</p>

CC BY-SA 3.0
2017-05-25T18:23:24.770Z
Algorithms do not have a complexity or membership in P or NP. The _problems_ that may be solved by various different algorithms, can be in P or NP, however.
Discrete lizard
CC BY-SA 3.0
2017-05-25T19:14:59.427Z
More specifically, only *decision problems* can be in P or NP.
xuq01
<lesson-ideas><complexity-theory>
Presenting Mapping Reducibility (for P vs NP)
# Presenting Mapping Reducibility (for P vs NP)

(Asked by: username_0 on 2017-05-25)

So, I am preparing to teach about P and NP for the first time. I know that I need to teach about Mapping Reducibility (aka One-to-One Reducibility). Can anyone recommend a set of algorithms that are easy to use to clearly illustrate the idea? The algorithms in this first brush with the topic don't, themselves, have to be NP - I just want to show a remapping that is extremely clear in order to impart the concept.

**Tags:** lesson-ideas, complexity-theory

> **Comments:**
> **username_1**: Algorithms do not have a complexity or membership in P or NP. The _problems_ that may be solved by various different algorithms, can be in P or NP, however.  
> **username_2**: More specifically, only *decision problems* can be in P or NP.  

---

## 2 answers

### Answer by username_2 on 2017-05-25. Score: 3 | Accepted answer

Considering that you teach HS students, many of the reduction examples "off the market" might be conceptually a bit too complex, and can be confusing even for many college students.

I'd suggest that you choose an example between very similar problems, like the (polynomial time) reduction from 4SAT to 3SAT.

So, what are 4SAT and 3SAT? SAT is the **Boolean satisfiability problem**, or, given a Boolean formula phi, we want to decide if there is a solution to the equation phi = true.

These equations are usually written in *conjunctive normal form*, or a series of conjunctions of disjunctions, like: "(a or b or c) and (c or d)". When each clause has 3 terms, the problem is called 3SAT. When each clause has 4, it's called 4SAT. Now you might get a sense how one could reduce from 4SAT to 3SAT. One possible reduction (which is extremely simple) is described [here](https://math.stackexchange.com/questions/571618/convert-4-sat-to-3-sat) on the Math SE.


---

### Answer by username_1 on 2017-05-25. Score: 1

A fairly simple reduction goes from Hamiltonian Cycle to the Travelling Salesman Problem (TSP).

The Hamiltonian Cycle problem on instance $G$ asks whether there exists a tour of some unweighted, undirected graph $G$.

TSP on instance $(G,k)$ asks whether there exists a tour in the weighted, complete graph $G$, of length at most $k$.

The reduction is as follows:  
Given the unweighted graph $G$, construct complete weighted graph $G'$ on the same vertices as $G$. Set the weights such that an edge in $G'$ has weight $0$ if the edge was in $G$ and set the weight to $1$ otherwise. The results of the reduction is the TSP instance $(G', 0)$.

Since any tour in $G'$ is of length zero if and only if it is a tour using only the vertices in $G$, it follows that the answer to the instance for TSP is 'yes' if and only if the answer to the instance for Hamiltonian Cycle is 'yes'.

Since this reduction can be computed in polynomial time, this also shows that TSP is NP-hard if Hamiltonian Cycle is NP-hard. (Both Hamiltonian Cycle and TSP are known to be NP-hard problems)


---

