## Certificate Verification for Costas Arrays

2014.04.25If 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:

DefinitionLet . has theCostas propertyiff

for all .

This is all we need. Here’s code.

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^{3}) 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.