7
$\begingroup$

In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&dq=np-hard+completing+hadamard+matrix&source=bl&ots=8sKv9bAtc8&sig=ITZSmtD2p2xr6Q4RDqhbQQk0NDI&hl=en&sa=X&ved=2ahUKEwiotuLdvfzdAhWBKHwKHUF9AO0Q6AEwB3oECAMQAQ#v=onepage&q=np-hard%20completing%20hadamard%20matrix&f=false, to give two ) it is claimed that determining the "equivalence" of two Hadamard matrices (in the sense of allowing sign-flips and permutations on rows and columns) is NP-hard. No source I found for this statement provided a citation, and I couldn't find any paper claiming to prove this.

On the other hand, https://core.ac.uk/download/pdf/82725146.pdf provides an $n^{O(\log n)}$ algorithm for identifying equivalent Hadamard matrices. This is somewhat to be expected, since Hadamard matrix equivalence is a lot like graph isomorphism. (It's also not hard to reformulate Hadamard matrix equivalence as a GI problem on $O(n^2)$ vertices directly, leading to a quasipolynomial solution under a variety of well-studied GI algorithms.)

If both of these claims were true, of course, this would be big news and violate the ETH. Is the claim of NP-hardness just a (false) folk theorem?

$\endgroup$
6
$\begingroup$

Both sources you cite are from the same author. Note the full quote:

For identifying the equivalence of two Hadamard matrices of order $n$, a complete search compares $(2^n n!)^2$ pairs of matrices and is known to be an NP-hard problem when $n$ increases.

I don't think the author knows what NP-hard entails and confuses it with simply exponential. Further evidence of this is that he states that a complete search (an algorithm) is NP-hard, when that is a property of a problem, not an approach or algorithm.

This source from a different author similarly misuses the term NP-hard:

The classification of Hadamard matrices of orders $n \geq 32$ is still remains [sic] an open and difficult problem since an algorithmic approach of an exhaustive search is an NP hard problem.

In fact the wording is very similar and found in a field study. It would surprise me if the source of this error wasn't the original paper(s) above being copied without thought.

Since these authors consistently seem to misunderstand the meaning of NP-hard, I think their claims (that come without proof or reference) can be safely dismissed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.