---
created_at: '2015-12-11T09:16:39.000Z'
title: Secret Santa is NP-Complete (2006)
url: http://blogs.msdn.com/b/steverowe/archive/2006/12/19/secret-santa-is-np-complete.aspx
author: caffeinewriter
points: 45
story_text: 
comment_text: 
num_comments: 17
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1449825399
_tags:
- story
- author_caffeinewriter
- story_10716112
objectID: '10716112'

---
Every year my group of friends undertakes a Secret Santa gift exchange. 
When we started we each drew names from a hat and bought a gift for the
names we drew.  Being budding programmers, we soon dispensed with the
hat and wrote a program to do the work for us.  In 1999 a friend and I
wrote a C++ app to do the work.  Though we've been running it every
year, the code hasn't much changed in the intervening seven years.  It
is getting dated and needs reworking. 

Toward that end, I've been contemplating the match routine lately.  The
current one does something naive like:

> Pick a person
> 
> Choose a match at random
> 
> If there is a conflict with that person, slide to the next one on the
> list.
> 
> Once a match is found, remove those people from the relative lists and
> pick a new person.
> 
> If a match cannot be made, start the process over.

With a small number of people and not a lot of blacklisting (husband
shouldn't draw wife's name, etc.), this algorithm will work.  However,
for a complicated list of people, this algorithm is nondeterministic and
could theoretically run forever.  I was thus searching for a better
algorithm.  One which was faster than a complete enumeration of all
options and deterministic in nature.

This weekend I took the final for my Formal Models of Computation
course.  (Yes, this ties in with the above--be patient) The last thing
we covered was complexity classes and the concepts of P and NP.  What
follows is a brief description of this concept.  For a more formal
handling of the subject, check out the Wikipedia
[entry](http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP). 

In theoretical computer science, they don't use real computers.  Rather,
they use formal models called [Turing
Machines](http://en.wikipedia.org/wiki/Turing_machines).  These have the
same power to solve problems that modern computers do, just a bit less
efficiently.  They are a good proxy for real computers.  The speed of
these machines is measured roughly in terms of the input.  So given an
input of length n, a [linear](http://en.wikipedia.org/wiki/Linear_time)
algorithm would take O(cn) time, where c is a constant.  We usually
ignore these constants and just call it O(n) time. 

There is a class of problems called P or
[Polynomial-time](http://en.wikipedia.org/wiki/Polynomial_time) which
represent those problems that can be solved by a Turing machine in a
time which is a polynomial of the input length.  That is, O(n^2),
O(n^3), ... , O(n^k).  These are generally thought of as those problems
that computers can efficiently solve.

There is another class of problems called NP or
Nondeterministic-Polynomial-time.  These represent those problems that
can be solved by a nondeterministic Turing machine in polynomial time. 
A nondeterministic Turing machine is bascially one that can do more than
one thing at once.  When it comes to a fork in the algorithm, it can
take both forks simultaneously. 

It is assumed that NP describes a bigger universe of problems than P. 
That is, P \!=NP.  What takes nondeterministic Turing machines
polynomial time takes regular Turing machines [exponential
time](http://en.wikipedia.org/wiki/Exponential_time).  That is, they
take something like O(2^n) time.

Back to my Secret Santa problem.  It was just after my final that I
turned my thoughts back to solving this problem.  It then hit me that
what I was trying to do was impossible.  There is a well-known NP-class
problem which involves finding a [Hamiltonian
circuit](http://mathworld.wolfram.com/HamiltonianCircuit.html).  A
Hamiltonian circuit is a path that traverses an entire graph by visting
each node exactly one time.  It turns out that this is exactly the
problem I was trying to solve.  Imagine my Secret Santa problem as a
graph where each person is a node and there are edges between all nodes
that are not blacklisted.  In this view of the problem, I'm trying to
find a path around the graph, visting each node once.  In theoretical
computer science this is known as a reduction.

This analysis pretty much dashes my chances of finding an elegant
solution to the problem.  There is no true solution other than brute
force trying each combination.  With the small number of nodes in my
usual matching, this works but I still want something better.  All is
not lost, however.  There are
some [techniques](http://www.densis.fee.unicamp.br/~moscato/Hamilton.html)
I can use to get close to the solution without necessarily trying all of
the combinations which I intend to investigate.  I'll write about them
after I understand more.

Wow.  I guess I did learn something practical in that class after all.
