Certificate Verification for Costas Arrays

2014.04.25

If you never heard of Costas arrays before you may want to watch this video.

First of all, I want to be clear with the way that I’m saying “Costas arrays” but I’m not really working with arrays. It’s more common to think of them as permutations.

This is the definition that I found the easiest to understand:

Definition Let $f\colon [n] \rightarrow [n]$ . $f$ has the Costas property iff

$f(i+k)-f(i) = f(j+k) - f(j) \implies i = j$

for all $i, j, k \in [n]$ .

This is all we need. Here’s code.

import itertools

def is_costas(f):
    n = len(f)
    return all(f[i+k]-f[i] != f[j+k]-f[j]
               for i, j in itertools.combinations(range(n), 2)
               for k in range(1, n-max(i, j)))

I was a bit more judicious instead of checking for every i, j and k like the definition says. There’s symmetry here and I tried to explore it by assigning i and j to elements of 2-combinations.

The definition leaves the restriction of k implicit, we need to make it explicit thus we keep k limited with max(i, j).

And lastly, you need to be careful with the fact that, in contrast with the definition, Python’s indexing is zero-based.

The decision problem of determining if there is at least one permutation of a given length n satisfying the Costas property is sometimes called CAP (Costas Array Problem). I just showed you an O(n³) certificate verification algorithm for this problem, so that means that CAP is in NP.

As far as I know it’s an open question if it’s NP-complete.

You can use this code to search for Costas arrays of a given n by checking permutations. In 6 minutes I could find all Costas arrays up to n=10. Using the same idea in a constraint programming solver I found all Costas arrays up to n=11 in 1 minute.

Victor Salgado

Certificate Verification for Costas Arrays