On the Complexity of the Verification of the Costas Property

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> In this paper, we show that in order to ascertain whether a permutation has the Costas property, only a restricted subset among the totality of pairs of entries in the same row of the difference triangle needs to be checked, and we explicitly describe such a subset. This represents a further refinement on the definition of a Costas permutation. This observation can be used to speed up algorithms that exhaustively search for Costas permutations. Asymptotically, the savings approaches 43% for large orders when compared with the previous standard efficient method. </para>