\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf E. R. Vaughan}
%
%
\medskip
\noindent
%
%
{\bf The Complexity of Constructing Gerechte Designs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Gerechte designs are a specialisation of latin squares. A gerechte
design is an $n\times n$ array containing the symbols $\{1,\dots,n\}$,
together with a partition of the cells of the array into $n$ regions
of $n$ cells each. The entries in the cells are required to be such
that each row, column and region contains each symbol exactly once. We
show that the problem of deciding if a gerechte design exists for a
given partition of the cells is NP-complete. It follows that there is
no polynomial time algorithm for finding gerechte designs with
specified partitions unless P=NP.



\bye