The complexity of constructing gerechte designs (Q1010920)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity of constructing gerechte designs |
scientific article |
Statements
The complexity of constructing gerechte designs (English)
0 references
7 April 2009
0 references
Summary: 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.
0 references
grechte designs
0 references
latin squares
0 references
partition of the cells of array
0 references