Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.
How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?
My favorite example to use with non-CS friends is this one:
Kidney exchange markets are essentially a restricted form of cycle cover. I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!
My second favorite example is the hospitals-and-residents problem (aka the college admissions problem). Each hospital ranks all residents (graduating medical students) and residents rank hospitals. Each hospital has a certain number of slots. From there it's a stable matching problem and can be solved in polynomial time.
But in reality, couples can enter the system (yes, there is indeed a system) together, so that the system won't, for example, split up married couples who are both applying for residency. The addition of couples makes the problem NP-complete. In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.
Some "every day" problems that are NP-hard, appropriately formulated:
Assigning university classes to timeslots to minimize scheduling conflicts.
Assigning wedding guests to seats so that friends sit at the same table, but enemies do not.
Planning a road trip to visit all of the tourist spots on a list, so as to minimize driving.
The traveling salesman problem is apparently accessible... at least where I am, this seems to be the most popular CS problem among non-CS folks by far. I also found the following illustration of Vertex Cover quite appealing, as introduced by my algorithms instructor:
You have a road network and wish to ensure that if a car is stuck out of fuel, there is a gas station on at least one end of the road.
As a city planner, you want to minimize costs by building the fewest number of gas stations possible. This is essentially the vertex cover problem, and I have found some success in pointing out that although you don't expect to find the optimal vertex cover in polynomial time, you can find something that is only a factor of two away in polynomial time, by simply picking up both endpoints of a maximum matching (well, that last detail might be omitted depending on how keen your audience is - especially since the MM algorithm isn't exactly a two-liner).
As for an example of a 'jump in complexity' with a small change in the nature of the problem, I think the difference between checking 2-colorability and 3-colorability makes a good example. With all the publicity surrounding the four-color theorem, one might also point out that checking whether a map can be properly colored with only three colors instead of four is hard, even though we know that it can always be colored with four colors. A fair number of people find this quite startling.
Another fairly natural situation is the deadlock recovery problem in operating systems. This is modeled by the NP-complete problem of feedback vertex set - the smallest number of vertices whose removal makes the graph acyclic - and I find this to be a remarkable example as well (and is explained further in that wikipedia article).
Knapsack is pretty easy to grasp, especially for anyone who has had to deal with a small suitcase.. a nice example if they know dynamic programming.
Another fun (practically identical) one is Subset-sum, because it also has a nice physical interpretation: imagine the numbers being the distances of equal point-masses on an ideal (massless) ruler, with the fulcrum at the origin. Subset-sum says: does there exist a non-empty subset such that the ruler will remain balanced? (i.e., such that the center of gravity is the support point for the ruler?)
In both cases, it seems intuitive that naive strategies may force resorting to checking all subsets.
If they have more background, it's nice to grow problems by dropping constraints. For example, starting with a max flow problem, turning it into a linear program, and making it an integer program. (A great one of course is MAX-CUT, since to people with more background you can also bring up UGC; I touch some of this in an MO answer https://mathoverflow.net/questions/33036/is-quadratic-programming-still-np-hard-if-you-have-bounds-and-a-feasible-point/33048#33048 .) Also there are neat things like problems seemingly similar which have vastly different complexity (Euler (edge) path is linear time, Hamiltonian (vertex) path is NP-complete).
I think parallel parking is NP-hard.
In fact, the more general problem of finding the shortest path with bounded curvature that takes a polygonal object from its initial position to its final position in a polygonal environment is NP-hard. The proof can be found here - http://portal.acm.org/citation.cfm?id=298976
Crossword puzzle construction is NP-Complete: Given a set of answers, try to fit them into a grid.
I created the website Tagxedo, http://www.tagxedo.com, a word cloud generator that fits words (sized by their frequencies) into shape. The results are very pretty, but the problem is easily proven to be NP-hard (packing problem).
Interestingly, many NP-hard problems have "easy" approximations. Tagxedo seems to be doing an almost perfect job in many cases. This leads to interesting discussion about the practical implication of P vs NP, and the topic of approximation.
One of my friends spent a sabbatical year watching a baseball game in every major league stadium in North America. Without flying. (He didn't quite succeed; three stadiums were under construction that year.)
Due to the success of companies like Uber and Lyft, many people have a very accessible direct experience with NP-complete problems.
Given a collection of drivers and a list of people who want to be picked up at various times, what is the most efficient allocation of passengers to drivers?
This problem (when suitably rephrased) is NPC and I imagine that people have at some point wondered how Uber decides to pair drivers and passengers.
I usually use SAT as an example. I say something like "all sorts of problems that come up all the time can be rewritten as looking for a true assignment to a big logic formula. The P vs NP question is whether is there a fundamentally easier way to solve this logic formula than just trying all possibilities. So far no one has been able to either find a way or prove that there is no easy way out".
An Np-complete problem like Sudoku (on nxn sqaure) is like a Universal tool which enables us to efficiently solve all problems that have efficiently verifiable solutions. The only requirement is to have an efficient method to solve Sudoku.
Scheduling is around us on an almost daily basis. Whether it be the workplace, manufacturing, or just planning your day, you'll find an $NP$-complete problem that you wish had an efficient exact algorithm. A situation that arises commonly in scheduling is parallel machine scheduling (typically non-preemptive, and tasks occur in parallel). A trivial way of visualizing parallel machine scheduling problems is stacking blocks.
For instance, finding an assignment of $n$ blocks of varying heights (say $p_j$) with $m$ towers (blocks are stacked to form) with the goal of minimizing the height of the tallest tower is $NP$-hard. This is equivalent to the makespan problem on identical parallel machines (replace tasks/jobs of length $p_j$ for blocks, towers for machines, and tallest height for the completion time of the machine that finishes last (called the makespan)). Asking if there is a tower of height at most $k$ would then be $NP$-complete in this situation. Observe that this doesn't need to be blocks providing we assume they can't topple over. It could be stacks of papers, crates, or plates.
Hope this helps!
A whimsically accessible example is a brief presentation by Mark Dominus (see the related blog post) called “My Favorite NP-Complete Problem” where the image below is the punchline of an overview of exact cover by 3-sets.
Titles in the video series include
The clear intent was for each video to contain three episodes all on a common theme drawn from a pool of topics of interest to young children.
The odd duck in the series was a video on “flowers, bananas, and … hair.”
I like to introduce Vertex-Cover as a problem in which the underlying graph models a museum, so that the vertices represent the museum rooms and the edges represent the corridors. Then, it is easy for the students to understand that minimising the number of guards required to watch over the museum corresponds to finding a vertex cover. The guards are placed at the doors of the selected rooms (vertices) and cover the corresponding corridors (edges).
Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit:
Number guessing, where you can only guess single numbers till you've got it right.