8

If your student has tried it once, you can use sudoku as an example (it does not work so well if the student has never heard of it). Given a completed sudoku grid, write a program that verifies that it is valid: your student can probably write this simple program in a few minutes, or if you give the answer see that it is really easy. Given an incomplete ...


6

Map coloring is a very nice example. It is NP to find if the graph is planar or not (you can reduce the map coloring if a graph is planar or not), but it is relatively easy to see if the colored map has <= 4 colors.


4

I wouldn't want to penalize kids who are really relatively inexperienced for not coming up with the fastest solutions on a test. Even if they're in 11th grade and have a couple of years under their belts, they likely haven't been in real situations where run time is important. If I were to want a specific run time on a test I'd say something like "for full ...


4

Start with the humor of xkcd: I used the above comic in a lecture on P vs. NP. The analogy I gave is eating at The Cheesecake Factory. Their menu boasts something like 250 dishes and 50 kinds of cheesecake. It's a tome to wade through. Now, imagine a scenario like this: You are given a $50 gift card to The Cheesecake Factory. You can order anything you ...


4

The subset sum problem is one that is easy to understand - "given this set of numbers {provide a set of a dozen or so}, is there a subset of these numbers that sum up to 100?" For example, the set 49, 55, 79, 67, 47, 12, 60, 84, 52, 44, 43, 47, 93, 68, 70, 96, 19, 22, 62, 79. Theres only one solution for the sum to 100: 12 19 22 47 Determining this will ...


3

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 ...


2

Complexity class NP_ is described here: https://en.wikipedia.org/wiki/NP_(complexity). One of the easiest examples to explain is given there as: The decision problem version of the integer factorization problem: given integers n and k, is there a factor f with 1 < f < k and f dividing n? It is easy to explain as most students will understand ...


2

Please note that all P problems are in NP too, since they are easy to solve and therefore also easy to verify. Maybe you are asking for an NP-complete problem. In that case I think the sudoku mentioned above is a good example if the student is familiar with that In a different case, the subset sum problem is my second option.


2

It seems that you are aiming to convey the significance of disproving ETH? If you're looking to leave some impression, it's always better to show rather than tell. I think your students need to see some examples of practical areas and difficult problems that efficiently reduce to SAT. If you can demonstrate to them that SAT is a "funnel" of sorts for many ...


1

I'm not sure I understand your dilemma, especially for the students you describe. Many computational problems can be shown to be "reducible" to others using a sub exponential (usually polynomial) run time algorithm. That is to say, a solution to one of these problems can be transformed into a solution of a different problem in polynomial time. The most ...


1

I recognize that this isn't exactly an answer to your question, but is a different way to think of the issue. I applaud the answer of Mike Zamansky given here already, but suggest an orthogonal approach. One way to get students to focus on efficiency is to ask them to name (or select from a list, perhaps) the efficiency of the solution they present and ...


1

First, note the difference between NP and NP-hard. NP simply means verifiable easily. NP-hard means verifiable easily, but also means that the problem is as hard to solve as the hardest problems in NP, which are not known to be easily solvable (see P = NP). For describing what it means for a problem to be NP-hard, I have had success by referring to the ...


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 ...


Only top voted, non community-wiki answers of a minimum length are eligible