Deciding Hadamard equivalence of Hadamard matrices
Tóm tắt
Equivalence of Hadamard matrices can be decided inO(log2
n) space, and hence in subexponential time. These resource bounds follow from the existence of small distinguishing sets.
Tài liệu tham khảo
J. Cooper, J. Milas, and W. D. Wallis,Hadamard equivalence, in:Combinatorial Mathematics (D. A. Holton and J. Seberry, eds.) Springer-Verlag (1978), 126–135.
L. M. Goldschlager,Synchronous parallel computation, Ph. D. thesis, University of Toronto, 1977.
J. E. Hopcroft and J. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley (1969).
J. S. Leon,An algorithm for computing the automorphism group of a Hadamard matrix, Journal of Combinatorial Theory A27 (1979), 289–306.
R. J. Lipton, L. Snyder, and T. Zalcstein,The complexity of word and isomorphism problems for finite groups, Tech. Rep. 91/76, Yale Univ., (1976).
B. D. McKay,Hadamard equivalence via graph isomorphism, Discrete Math. 27 (1979), 213–214.
W. D. Wallis and J. Wallis,Equivalence of Hadamard matrices, Israel J. Math. 7 (1969), 122–128.