article.tex

\documentclass[runningheads]{llncs}

\usepackage{amsmath}
\usepackage{url}
\usepackage{graphicx}
\usepackage{salgorithm}
\usepackage{verbatim}

\newcommand{\newword}[1]{{\bf #1}}
\newcommand{\NP}{\ensuremath{\mathcal{NP}}}
\newcommand{\Instance}{{\sc Instance~}}
\newcommand{\Question}{~\\
{\sc Question~}}
\spnewtheorem{prob}[theorem]{Problem}{\bfseries}{\itshape}

\title{Using Cell Phone Keyboards is (\NP) Hard}
\author{Peter Boothe}
\institute{Manhattan College\\
\email{peter.boothe@manhattan.edu}
}

\begin{document}
\maketitle

\begin{abstract}
Sending text messages on cell phones which only contain the keys 0 through 9
and \# and * can be a painful experience.  We consider the problem of designing
an optimal mapping of numbers to sets of letters to act as an alternative to
the standard $\{2\to\{abc\}, 3\to\{def\}\ldots\}$.  Our overall goal is to
minimize the expected number of buttons that must be pressed to enter a message
in English.  Some variations of the problem are efficiently solvable, either by
being small instances or by being in \ensuremath{P}, but the most realistic
version of the problem is \NP\ hard.  To prove \NP-completeness, we describe a
new graph coloring problem {\sc UniquePathColoring}.  We also provide numerical
results for the English language on a standard corpus which describe several
mappings that improve upon the standard one.  With luck, one of these new
mappings will achieve success similar to that of the Dvorak layout for computer
keyboards.
\end{abstract}

Typing on a keyboard which has fewer keys than there are letters in the
alphabet can be a painful task.  There are a plethora of input schemes which
attempt to make this task easier (e.g. \cite{hcimethods,ordering1,godfest} and many more), but the one thing they have in common is
that all of these input methods use the standard mapping of numeric keys to
alphabetic numbers of 
$\{2\to\{abc\}, 3\to\{def\}, 4\to\{ghi\}, 5\to\{jkl\}, 6\to\{mno\}, 7\to\{pqrs\}, 8\to\{tuv\}, 9\to\{wxyz\}\}$.
We will consider schemes of rearranging the numbers on the keys to
make messages easier to type.  Most variants of this problem turn out to be
NP-hard, unfortunately.

Before we get any farther, let us sketch the basic problem that we will keep
revising and revisiting.  \begin{prob}[{\sc
MinimumKeystrokes}]~\\ \Instance\ A set of letters corresponding to an alphabet
$A$ $(|A| = n)$, a number of keys $k$, an input method $\mathrm{IN}$, and a set
of tuples of words and frequencies $W$.  The frequencies in $W$ are integers,
and the words are made up of solely of elements of $A$.  We will treat $\mathrm{IN}$ as
a function which, given a partition of $A$ and a word $w$, returns how many
keystrokes are required to type $w$.

\Question\ What is the best partition of $A$ into $k$ sets, such that the
total number of keystrokes to type every word in $W$ its associated frequency
times is minimized?  Equivalently, what is the partition of $P$ of $A$ ($|P| = k$) that
will minimize
$$\sum_{(w,f)\in W} f*\mathrm{IN}(w,P)$$
\label{probtemplate}
\end{prob}


We will consider two different real-world schemes for $\mathrm{IN}$ (basic
typing and T9), and for each variant or sub-variant that is proven \NP-hard, we
consider the restriction on $P$ that requires that we keep the alphabet in
alphabetical order.  In all cases where it is computationally feasible we
provide results for the case of the English language, on 8-key keyboards, using
the British National Corpus\cite{bnc} (BNC).  One feature of note is that no
matter what scheme we use, the problem is trivial if the number of keys is not
smaller than the number of letters in the alphabet ($k \ge |A|$).  Using tiny
keyboards is only (computationally) difficult when the keyboards do not have
enough keys.

\section{Setting a Baseline with the Easiest Problem}

The baseline we compare against is the most painful method of text entry.  In
this method, to type an `a', the user of the cellphone types the `2' key; to
type a `b' they type `22', to type `c' they type `222', to type a `d' they type
`3', to type an `e' they type `33', and so on.  To type a word with multiple
letters that use the same key, such as `accept', the user must pause between
keystrokes.  Thus, the full key entry sequence for `accept', using `.' to
indicate a pause, is `2.22.223378'.

\begin{figure}[t]
\begin{center}
\includegraphics[width=2in]{phonekeys.jpg}
\end{center}
\caption{A cell phone keyboard. Each key is mapped to a letter sequence: $2 \to (abc), 3\to (def), 4\to (ghi), 5\to (jkl), 6 \to (mno), 7 \to (pqrs), 8\to (tuv), 9\to (wxyz) $}
\label{keypic}
\end{figure}

We will neglect the pauses and concern ourselves solely with the number of
keystrokes required.  This layout and input method imply that `a' will always
require one button press, `b' will always require two, and so on.  Thus, to get
a baseline of how many keystrokes are required to enter the entirety of our
corpus of words $W$, we count the total number of occurrences of each letter,
and multiply that number of occurrences by the number of button pushes required
by that letter.  Running this on the British National Corpus using the standard
cell phone keyboard layout, we find that entering the entirety of the
100,106,029 word occurrences in the corpus would require 948,049,046 button
presses.  

If we examine a cell phone keyboard (Fig.~\ref{keypic}) then we observe some terrible design choices.  The frequently-occurring letters
'r' and 's' require more keystrokes than 'q'!  Surely, a better designed
keyboard can do better than this.  If we just reversed the order of the letters
on the 7 key, from `pqrs' to `srqp', the number of button presses required
would drop to 865,118,331 --- a savings of more than $8.7\%$.  If we assume
that every button press takes an equal amount of time, then this corresponds
the users spending $8.7\%$ less time entering their text messages.  In an
effort to discover how great these savings can be, we define the problem {\sc
BasicCellPhoneTyping} based on the template problem on
page~\pageref{probtemplate}.

\begin{prob}[{\sc BasicCellPhoneTyping}]~\\
\Instance\ A set of letters corresponding to an alphabet $A$ $(|A| =
n)$, a number of keys $k$, and a set of
tuples of words and frequencies $W$.  The frequencies in $W$ are integers,
and the words are made up of solely of elements of $A$. 

\Question\ What is the best partition $P$ of $A$ into $k$ sequences, such
that the total number of button presses to type every word in $W$ its
associated frequency times is minimized?  The number of button presses is equal
to the order of the letter in the sequence assigned to a given key.  For
example, in the key $2\to\{abc\}$, $a$ requires one keystroke and $c$ requires
3.  Equivalently, if we denote the number of button presses required to type
letter $a$ with partition $P$ as $\mathrm{IN}_P(a)$, then we want to find the $P$ that
minimizes $$\sum_{(w,f) \in W}\sum_{c\in w} \mathrm{IN}_P(c) * f$$
\label{bcpt}
\end{prob}

\begin{figure}
\begin{algorithm}
\Algorithm{GreedyBasicCellPhoneTyping}~$(A, k, W)$\+\\
    // $A$ is the set of letters \\
    // $k$ is the number of keys \\
    // $W$ is a set of pairs of words and their corresponding frequencies \\
    lettercount $\gets$ new\_map() \\
    \For $c \in A$\+\\
        lettercount$[c] \gets 0$\-\\
    \For (word, frequency) $\in W$\+\\
        \For $c \in$ word \+\\
            lettercount$[c] \gets $ lettercount$[c] +$frequency\-\-\\
    ordered $\gets \left[ ({\rm lettercount}[c], c)~\For c \in {\rm lettercount} \right]$\\
    sort(ordered)\\
    keys $\gets$ a array of length $k$ where each element is an empty list\\
    \For $i \gets 0 \ldots length($ordered$)$\+\\
        (count, char) $\gets$ ordered$[i]$\\
        append(char, keys$[i\mod k]$)\-\\
    \Return keys
\end{algorithm}
\caption{The greedy algorithm for Prob.~\ref{bcpt}.}
\label{greedyalg}
\end{figure}

To solve {\sc BasicCellPhoneTyping} we construct a provably optimal
greedy algorithm which works in time $O(|W| + |A| \log |A|)$.  Our algorithm is
detailed in Fig.~\ref{greedyalg}, and involves creating a histogram of the
letters, and then assigning letters to keys round-robin style in the order from
most-popular to least-popular.  To prove optimality, we invoke an exchange argument.

\begin{theorem}
The greedy algorithm finds an optimal solution to {\sc BasicCellPhoneTyping}.
\label{basicthm}
\end{theorem}
\begin{proof}
We will assume, for simplicity of proof, that all letters occur a different
number of times in the corpus.  We begin by comparing two assignments of
letters to keys by, for each assignment, constructing a sequence of sets, or
spectrum, $S$.  The set $S_1$ (layer 1) is the set of all letters which require
a single button press (that is, they are the first letter in their sequence on
their assigned key), $S_2$ (layer 2) is the set of all letters which require
two button presses, and so on.  If two assignments have equal spectra, then one
assignment may be transformed into the other assignment simply by swapping
letter between keys without increasing or decreasing the total number of button
pushes required to enter the corpus of words.   Two assignments are isomorphic
iff their spectra are equal.

Now assume for the sake of contradiction that we have assignment $D$, with
spectrum $T$, that is not isomorphic to the greedy solution $G$ with spectrum
$S$.  In a spectrum resulting from the greedy algorithm, all letters at
layer $i$ occur strictly more frequently than the letters at layer $j$, $j >
i$.  Also, in $S$, for all layers $i$ except for the last layer, $|S_i| = k$.
Because $T$ and $S$ are not isomorphic, in $T$ there must be at least one layer
$i$ such that $T_i \neq S_i$.  Let $T_i$ be the first layer for which that is
true.

There are two cases for layer $T_i$.  In the first case, $|T_i| < k$, and we
may remove any element from a later layer place it in layer $T_i$ and create a
strictly better layout.  In the second case, there is some letter $a$ such that
$a \in T_i$ and $a \not\in S_i$.  We choose the least-frequent such $a$.
Because the greedy layout algorithm creates layers in order of frequency, we
know that the frequency of $a$ is less than that of some letter $b$ in layer
$T_j$, $j>i$.  Therefore, by creating a new layout with $a$ and $b$ swapped
between $T_i$ and $T_j$, we have strictly decreased the number of button
presses.  Therefore, in both cases, $T$ was not an optimal layout, and we have
reached our contradiction.  \qed \end{proof}

For the BNC, the optimal layout has the spectrum $$[\{etaoinsr\}, \{hldcumfp\},
\{gwybvkxj\}, \{qz\}]$$ and any layout with that spectrum requires 638,276,114
button presses to entire the entire BNC instead of our original requirements of
948,049,046.  This represents a savings of $32.67\%$ over our original layout,
but only for the users who type using this most basic of input methods.
Unfortunately, this is the group of users who are likely the least adaptable to
change, as almost all ``digital natives'' use predictive methods to input text
messages\footnote{I have no statistics on this except for an informal survey of
one of my classes.  In that class, every student who used SMS either had a
cellphone with a 26+ key alphabetic keyboard or used a predictive method.}. 
To place the least burden of ``newness'' on these users while still
decreasing the number of button presses, we now consider schemes where the only
alteration of the keyboard is the rearrangement of the sequence of letters for
a given key.

By an argument symmetric to the proof of Theorem~\ref{basicthm}, we find that
the optimal layout in this new scheme is to place the letters of a given key in
sorted order, according to frequency.  Thus, the keyboard layout changes to
$2\to[acb], 3\to[edf], 4\to[ihg], 5\to[lkj], 6\to[onm], 7\to[srpq], 8\to[tuv],
9\to[wyxz]$ and requires 678,547,463 button presses to enter the whole corpus.
This layout represents a $28.43\%$ savings, and it has the added benefit that
it does not change which key is mapped to which set of letters.  This makes it
\newword{legacy preserving}, as creating a keyboard with this layout will not
invalidate such advertising gems as 1-800-FLOWERS.  Thus, we can speed up users
by $28.43\%$ (neglecting inter-letter pauses) and not undermine more than half
a century of advertising.  This layout represents perhaps the most plausible
layout yet\footnote{The described layout is the only legacy preserving layout
in this paper, and therefore should be considered the most practical
suggestion.  It also has the added benefit of not angering any of the
organizations behind the numbers 1-800-FLOWERS, 1-800-THRIFTY, and
1-800-MARINES}.  After setting up this baseline for the easy problem, we turn
our attention to optimizing cellphone keyboards for predictive input methods.

\section{The T9 Input Method}

In an effort to minimize the pain of cellphone keyboard typing, cellular
telephone manufacturers have created the T9 input method, which attempts to
guess which letter (of the three or four possible) is intended when a user hits
a single key.  Enhancements of this input method also provide speculative
lookahead to report, at any given time, what word it is that the user is most
likely trying to enter and provide a completion.  Unfortunately, because there
are fewer keys on the cellphone keyboard than there are letters in the English
alphabet, there are words which have different spellings but the same input
sequence.  As an example, in the traditional mapping of keys to characters both
`me' and `of' have the input sequence `63'.  Two words with the same input
sequence force the user to press a third button to cycle through the
possibilities in order from most likely (`of') to least likely (`me').  Even
worse: `home', `good', `gone', `hood', `hoof', `hone', and `goof' all have the
input sequence `4663'.  If the * key is used as the ``next match'' button, then
the user will have to type in `4663******' to type in the word `goof',
for a total of 10 button presses --- exactly the same number of button presses
required using the default layout and the basic input method, and three more
button presses than is required when using the basic input method with an
optimized layout.

When two words have the same input sequence (neglecting the *'s at the end)
then these words are \newword{t9onyms}.  When two or more words are t9onyms,
then the less-popular words require extra key presses, raising the expected
number of key presses to type in our corpus.  To type a given word, one
must press one button for every character in the word, followed by pressing
the * key as many times as there are t9onyms which are more likely than the
desired word.  Because typing on a cellphone keyboard is already an unpleasant
experience, we would like to minimize the expected number of keystrokes.  The
number of keystrokes a word requires is equal to the number of letters in the
word, plus the number of t9onyms which are more frequent than the word.
Formally, we extend Prob.~\ref{probtemplate} and define the {\sc
MinimumT9Keystrokes} problem as:

\begin{prob}[{\sc MinimumT9Keystrokes}]~\\
\label{thm:minstrokes}
\Instance\ An alphabet $A$, a set of words and their associated frequencies
$W$, and a number of keys $k$ ($|A| > k$).

\Question\ What is the partition $P$ of $A$ into $k$ sets which minimizes the
total button presses required to enter the entire corpus using the T9 input
method?
\end{prob}

and the corresponding decision problem is

\begin{prob}~\\
\label{minstrokesdecision}
\Instance\ A set $A$, a set $W$ of sequences of elements of $A$, a mapping $f$ from sequences in $W$ to the integers, and a number $t$.

\Question\ Is there a partition $P$ of $A$ into $k$ sets such that, if we denote $P(w)$ as the sequence of partitions $[p_i | w_i \in p_i, p_i \in P]$,
$$\sum_{w\in W} (\mathrm{len}(w)+\mathrm{order}(w,P,W,f)) * f(w) \le t$$
where len$(w)$ is the length of the sequence $w$ and order$(w,P,W,f)$ is the size of $\left\{s\in W | P(s) = P(w) \land f(s) \le f(w) \land s < w \right\}$, which is the set of sequences which map to the same sequence of partitions, but are not more popular, and are lexicographically smaller than $w$.
\end{prob}

This problem is in \NP, as any assignment may be verified to require
fewer than $t$ button pushes in time proportional to the total length of all
the words in $W$.  To prove completeness, however, we first prove the
\NP-completeness of an intermediate problem: {\sc UniquePathColoring}.

\begin{prob}[{\sc UniquePathColoring}]~\\
\label{upcolor}
\Instance\ A graph $G=(V,E)$, a set of paths $P$, and a parameter $k$.  A path
$p$ is a sequence of vertices in which adjacent vertices in $p$ are also
adjacent in the edge set $E$.

\Question\ Is there a $k$-coloring of $G$ such that every path $p\in P$ has a
unique coloring?  If we consider the coloring function $\chi(v)$ to map
vertices to colors, then we can extend this notation by having $\chi(p)$ map a
path $p = [ v_1, v_2, \ldots ]$ to the sequence $\chi(p) = [ \chi(v_1),
\chi(v_2), \ldots ]$.  Is there a coloring $\chi$ of $V$ such that 
    $$|\left\{ \chi(p)~\forall p \in P\right\}| = |P|\enspace ?$$
\end{prob}

\begin{theorem}{\sc UniquePathColoring} is \NP-complete.\end{theorem}
\begin{proof}
To prove that {\sc UniquePathColoring} is \NP-complete, we begin by noting that
any coloring of $V$ may be verified, in polynomial time, to map each path to a
unique sequence of colors.  Therefore, the problem is in \NP.  To prove
completeness, we reduce from {\sc GraphColoring}\cite{gandj}.

An instance of {\sc GraphColoring } consists of a graph $G=(V,E)$ and a
parameter $k$.  We then ask the question of whether there is a $k$-coloring
$\chi$ of the vertices of the graph such that $\forall (u,v)\in E$, $\chi(u)
\neq \chi(v)$.  We transform an instance of {\sc GraphColoring} into an
instance of {\sc UniquePathColoring} in the following manner:

Given $G=(V,E)$ and $k$ from {\sc GraphColoring}, we create $$G'=\left(V \cup
\{0,1\}, E \cup \{(0,1), (1,0), (0,0), (1,1)\} \cup \{ (v, 0)~ \forall v \in V\} \right)$$ We then
uniquely number each edge in $E$ with the numbers $1 \ldots |E|$.  For each
edge $e = (u,v)$ numbered $i$, we create the path set 
\begin{eqnarray*}
p_i &=& \{[v,0,b_1(i),b_2(i), b_3(i), \ldots b_{\lceil \log_2 i\rceil}], \\
    & &  ~[u, 0,b_1(i),b_2(i), b_3(i), \ldots b_{\lceil \log_2 i\rceil}]\} \\
\end{eqnarray*}
where $b_1(i)$ is the first digit of $i$ in binary, $b_2(i)$ is the second
digit of $i$ in binary, and so on.  Now we create our path set $$P = \{ [0,1],
[1,0] \} \cup \bigcup_{i = 1}^{|E|} p_i \enspace .$$ We then ask the question
of whether $G'$ and $P$ can be unique-path colored using only $k$ colors.

If there is a $k$-coloring $\chi$ of $G$, then we use that coloring to generate
a $k$-unique-path coloring of $G'$ and $P$ in the following manner: First,
assign vertices $0$ and $1$ different colors from the range of $\chi$.  Next,
assign each vertex to the color it received in the $k$-coloring of $G'$.  Now,
every element of our path set corresponds to a unique color sequence.  $[0,1]$
and $[1,0]$ are the only sequences of length two, and because we assigned these
two vertices different colors, $\chi([0,1]) \neq \chi([1,0])$.  If path $x$ and
path $y$ are not from the same $p_i$, then they have a different sequence of
zeroes and ones.  Therefore, because $0$ and $1$ are assigned different colors,
the only possible path that a given path in some $p_i$ might be confused with
is the other path in that $p_i$.  But each $p_i$ corresponds to an edge in
$E$, and we know for all edges in $(u,v) \in E$ that $\chi(u) \neq \chi(v)$.
Therefore, both paths within a given $p_i$ also have a distinct color sequence.
Therefore, given a $k$-coloring of $G$, we can generate a $k$-unique-path
coloring of $G'$ and $P$.

Now we prove that given a $k$-unique-path coloring of $G'$ and $P$ we can
create a $k$-coloring of $G$.  Given a $k$-unique path coloring, we are
guaranteed that no path in $P$ has the exact same coloring as any other path in
$P$.  This means that, for all $i$, the two paths in $p_i$ are distinct.  The
only difference between the two paths in $p_i$ is in the first vertex of the
path.  Therefore, for every $p_i$, the vertices of corresponding edge in must
be given distinct colors, and this is true for all $i$ and $e \in E$.
Therefore, for all $(u,v)\in E$, the color assigned to $u$ is distinct from the
color assigned to $v$.  Therefore, from a $k$-unique-path coloring of $G'$ and
$P$, we have a $k$-coloring of $G=(V,E)$.

\qed 
\end{proof}

This proof implies not just that {\sc UniquePathColoring} is \NP-complete, but that it is \NP-complete even when we restrict ourself to just 3 colors, because the number of colors in the {\sc UniquePathColoring} is exactly equal to the number of colors in the instance of {\sc GraphColoring}, and 3-coloring a graph is an \NP-complete problem\cite{3color}.

Now that we have proven {\sc UniquePathColoring} to be \NP-complete, we
immediately use it in a reduction.  
\begin{theorem}{\sc MinimumT9Keystrokes} (as specified in
Problem~\ref{minstrokesdecision}) is \NP-complete.  \end{theorem}

\begin{proof}
As we noted on page~\pageref{minstrokesdecision}, {\sc MinimumT9Keystrokes} is
in \NP.  To prove completeness, we reduce from {\sc UniquePathColoring}.  An
instance of {\sc UniquePathColoring} consists of a graph $G=(V,E)$, a set of
paths $P$, and a parameter $k$.  We then ask the question of whether there is a
vertex coloring of $G$ using $k$ colors where each path in $P$ ends up with
a unique sequence of colors.

We transform an instance of {\sc UniquePathColoring} into an instance of {\sc
MinimumT9Keystrokes} in the following way:  We make $A$ be the set of vertices
$V$, and we make $W$ be the set of paths $P$, and we assign each of these new
`words' a frequency of 1.  We then ask the question of whether there exists a
partition of $A$ into $k$ sets such that the total number of button presses
required is no greater than $t=\sum_{w\in W} \mathrm{len}(w)$.

Now we prove that if there is a {\sc UniquePathColoring} using $k$ colors, then
there exists a solution to the corresponding instance of {\sc
MinimumT9Keystrokes}.  In particular, a $k$-unique-path coloring if $G$ give us
a partition of the vertices $V$ into $k$ sets.  We map each set to a single key
in our solution to {\sc MinimumT9Keystrokes}.  Because each path has a unique
coloring, each word in the corresponding {\sc MinimumT9Keystrokes} has a unique
pattern of button presses.  Therefore, the number of more popular words with
the same keystrokes as a given word is exactly zero.  Thus, because each word
in the corpus has a frequency of one, to type in the entire corpus only
requires exactly as many keystrokes as there are words in the corpus, and
therefore, the $k$ unique path coloring of $V$ corresponds exactly to an
assignment of letters to keys such that the total number of keystrokes is
exactly $\sum_{w\in W} \mathrm{len}(w)$, which is exactly $t$.

Next, we prove that a solution to the {\sc MinimumT9Keystrokes} problem
instance implies a solution to the corresponding {\sc UniquePathColoring}
problem.  If there exists a partition of $A$ into $k$ partitions such that
$$\sum_{w\in W} (\mathrm{len}(w)+\mathrm{order}(w,P,W,f))*f(w) \le t =
\sum_{w\in W} \mathrm{len}(w)$$ then, because $f(w) = 1$, $ \forall w \in W$,
it must be true that $\mathrm{order}(w,P,W,f) = 0$,  $\forall w \in W$.
Therefore, every word $w \in W$ has a unique sequence of button presses if we
partition $A$ into $k$ partitions according to $P$.  To generate our
$k$-unique-path coloring of $G$, we color each set in $P$ a single unique
color.  Because each word in $w$ has a unique sequence of partitions, each path
has a unique coloring, and therefore we can color the corresponding instance of
$G$ using $k$ colors.  Thus, a partition of $V$ into $k$ partitions which allows the corpus to be entered in less than $t$ keystrokes implies a $k$-unique path coloring of $G$.  Therefore, because {\sc UniquePathColoring} can be reduced to {\sc MinimumT9Keystrokes} and is in \NP, {\sc MinimumT9Keystrokes} is \NP-complete.
\qed
\end{proof}

This proof of \NP-completeness is of a relatively strong form: just like {\sc UniquePathColoring}, our problem remains \NP-complete even if we restrict ourselves to $k=3$ (only 3 buttons on the cell phone keyboard).

Because our problem is \NP-complete, we will not try to find a general solution.  In our specific instance, with 26 letters and an eight key keyboard (1 and 0 are reserved for other uses),  we must choose the best layout from among $$\binom{26}{8} \binom{18}{8} \binom{10}{8} = 3,076,291,325,250$$ different possibilities.  Given that, currently, it takes around a tenth of a second to count the button presses required to enter the BNC, an exhaustive search will take 307,629,132,525 seconds, or 9.75 millennia.  Therefore, we have two remaining avenues of attack: find the best answer possible using stochastic methods, or solving a simpler problem.  Using stochastic methods (a simple genetic algorithm), the best layout we found was 
$$\{\{eb\}, \{lcd\}, \{sh\}, \{zmx\}, \{fayg\}, \{toj\}, \{unpv\}, \{irkwq\}\}$$
which required 441,612,049 button presses to enter the entire corpus.  Our genetic algorithm was quite simple: From an initial gene pool of random layouts, we discarded all but the best layouts (the survivors).  Then, we added to the gene pool random mutations of the survivors to fill out the gene pool back to its original size, and repeated the process of selection and mutation for some time.  As compared to the requirements of the default layout (443,374,079), this represents a savings of less than 1\%, and is thus not a very attractive alternative to existing layouts.  This low amount of improvement, while not good news for our proposed reordering, is excellent news for all current cell phone users: the default cell phone keyboard layout seems relatively efficient for T9 text entry in English!

\subsection{Alphabetic Order}

Our arbitrary remappings of the keyboard may be quickly deemed unusable, simply
because it is almost impossible to tell where a given key is located without
memorizing the entire new layout.  Therefore, we define a refinement of the
keyboard layout problem, in which the characters are required to be kept in
alphabetical order as a sequence, and our only choices are about how to divide
the subsequence into key assignments.  The default layout can be described as
the partition
$abc|def|ghi|jkl|mno|pqrs|tuv|wxyz$.  Is this partition optimal?  To
decide this, we define the problem {\sc MinimumKeystrokePartition} as:
\begin{prob}[{\sc MinimumKeystrokePartition}]~\\
\label{thm:minpartition}
\Instance\ A sequence of letters $A = \{a_1, a_2, \ldots \}$, a set of words and their associated probabilities $W$, and a set of keys $K = \{2, 3, 4, \ldots \}$ ($|A| > |K|$).

\Question\ What is the mapping $f$ of $A \to K$ which minimizes the expected number of characters to type a word from $W$, and where $f(a_1) = 2$ and if $f(a_i) = k$, then either $f(a_{i+1}) = k$ or $f(a_{i+1}) = k+1$?
\end{prob}

The number of partitions of a sequence of size $n$ into $k$ subsequences is equal to $\binom{n-1}{k-1}$, and in the particular case of the 26 letter alphabet and the eight keys available on a cell phone keyboard, we find that there are $\binom{26-1}{8-1} = 480,700$ possible sequences.  This means that, in the case of our corpus which requires tenths of a second to test against a proposed solution, we can test every possible sequence in just 480,700 seconds.  Therefore, our final result comes from simply generating and testing every single partition of the alphabet into 8 sets.  We found that the best partition was 
$$\{\{ab\}, \{cde\}, \{fghij\}, \{klm\}, \{nop\}, \{qrs\}, \{t\}, \{uvwxyz\}\}$$
which required 442,717,436 button presses, yet again for a savings of less than 1\% over the default layout.

\section{Conclusion}

We have developed three problems based on the idea of making cell phone keyboard more efficient for typing text messages.  Different text entry methods yield problems with very different levels of solvability.  If we restrict ourselves to the basic text entry method, then a greedy algorithm will work for finding the optimal layout.  Even better, the greedy algorithm works whether we want to restrict ourselves to rearranging the order of letters on a single key, or to rearranging all letters on all keys.  On the other hand, if we try to optimize against the more complex T9 input method, then we find that the problem is \NP-complete.  After proving completeness, we gave numerical results which indicate that it will be difficult (or perhaps impossible) to significantly improve on the default layout of letters.  This stands in sharp contrast to the simpler input method, where we were able to improve by more than 27\% just by reordering the letters on the keys, but never moving a letter from one key to another.

We have also discovered a new \NP-complete problem {\sc UniquePathColoring}, which may be of use in other contexts.  In particular, it is rare in the literature to find an \NP-complete problem that contains both partitions and sequences, which is why we had to invent a new one here.  The hope, as always, is that this problem will prove useful to others.

We left as future work any exploration of the issue of needing to pause between
letters in the basic typing method, and, while there do exist even more
sophisticated input methods\cite{hcimethods}, we have left them unmentioned and unexamined.  Optimizing a keyboard for the basic text input method was relatively straightforward, but, for the T9 input method, optimally using a cell phone keyboard is \NP\ hard.

\bibliographystyle{abbrv}
\bibliography{bibliography}

\newpage
\appendix
\section{A Genetic Algorithm for Discovering Efficient T9 Layouts}
{\tiny
\verbatiminput{genetic.cpp}
}

\section{Code for Analyzing All Alphabetic-Order T9 Layouts}
{\tiny
\verbatiminput{notrcount.cpp}
}
\end{document}