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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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. $\endgroup$– Discrete lizardMay 25, 2017 at 18:23
-
$\begingroup$ More specifically, only decision problems can be in P or NP. $\endgroup$– xuq01May 25, 2017 at 19:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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 on the Math SE.
$\begingroup$
$\endgroup$
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)
