Ist die Unterscheidung von Hadamard-Matrizen wirklich NP-schwer?

An verschiedenen Stellen ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf und 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 , um zwei zu ergeben) Es wird behauptet, dass die Bestimmung der "Äquivalenz" von zwei Hadamard-Matrizen (im Sinne des Zulassens von Vorzeichenflips und Permutationen in Zeilen und Spalten) NP-hart ist. Keine Quelle, die ich für diese Aussage gefunden habe, lieferte ein Zitat, und ich konnte kein Papier finden, das behauptet, dies zu beweisen.

Auf der anderen Seite bietet https://core.ac.uk/download/pdf/82725146.pdf eine$n^{O(\log n)}$Algorithmus zur Identifizierung äquivalenter Hadamard-Matrizen. Dies ist etwas zu erwarten, da die Hadamard-Matrixäquivalenz dem Graphisomorphismus sehr ähnlich ist. (Es ist auch nicht schwer, die Hadamard-Matrixäquivalenz als GI-Problem neu zu formulieren$O(n^2)$ Scheitelpunkte direkt, was zu einer Quasipolynom-Lösung unter einer Vielzahl gut untersuchter GI-Algorithmen führt.)

Wenn diese beiden Behauptungen wahr wären, wäre dies natürlich eine große Neuigkeit und würde die ETH verletzen. Ist die Behauptung der NP-Härte nur ein (falscher) Volkssatz?

Beide von Ihnen zitierten Quellen stammen vom selben Autor. Beachten Sie das vollständige Zitat:

Zur Identifizierung der Äquivalenz von zwei Hadamard-Ordnungsmatrizen $n$vergleicht eine vollständige Suche $(2^n n!)^2$ Paare von Matrizen und ist bekanntermaßen ein NP-hartes Problem, wenn $n$ erhöht sich.

Ich glaube nicht, dass der Autor weiß, was NP-hard bedeutet, und es einfach exponentiell verwechselt. Ein weiterer Beweis dafür ist, dass er angibt, dass eine vollständige Suche (ein Algorithmus) NP-hart ist, wenn dies eine Eigenschaft eines Problems ist, kein Ansatz oder Algorithmus.

Diese Quelle eines anderen Autors missbraucht in ähnlicher Weise den Begriff NP-hard:

Die Klassifizierung von Hadamard-Ordnungsmatrizen $n \geq 32$ ist immer noch ein offenes und schwieriges Problem, da ein algorithmischer Ansatz einer erschöpfenden Suche ein hartes NP-Problem ist.

Tatsächlich ist der Wortlaut sehr ähnlich und wurde in einer Feldstudie gefunden. Es würde mich überraschen, wenn die Ursache für diesen Fehler nicht das Originalpapier wäre, das oben ohne nachzudenken kopiert wurde.

Da diese Autoren die Bedeutung von NP-hard immer wieder falsch zu verstehen scheinen, denke ich, dass ihre Behauptungen (die ohne Beweise oder Hinweise kommen) sicher zurückgewiesen werden können.