Is Code Equivalence easy to decide?

被引:70
作者
Petrank, E [1 ]
Roth, RM [1 ]
机构
[1] HEWLETT PACKARD LABS,PALO ALTO,CA 94304
关键词
Code Equivalence; Graph Isomorphism; interactive proofs; polynomial hierarchy;
D O I
10.1109/18.623157
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We study the computational difficulty of deciding whether two matrices generate equivalent linear codes, i.e., codes that consist of the same codewords up to a fixed permutation on the codeword coordinates. We call this problem Code Equivalence. Using techniques from the area of interactive proofs, we show on the one hand, that under the assumption that the polynomial-time hierarchy does not collapse, Code Equivalence is not NP-complete. On the other hand, we present a polynomial-time reduction from the Graph isomorphism problem to Code Equivalence. Thus if one could find an efficient (i.e., polynomial-time) algorithm for Code Equivalence, then one could settle the long-standing problem of determining whether there is an efficient algorithm for solving Graph Isomorphism.
引用
收藏
页码:1602 / 1604
页数:3
相关论文
共 15 条
[1]  
[Anonymous], 1992, DISCRETE MATH
[2]   ARTHUR-MERLIN GAMES - A RANDOMIZED PROOF SYSTEM, AND A HIERARCHY OF COMPLEXITY CLASSES [J].
BABAI, L ;
MORAN, S .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 36 (02) :254-276
[3]  
BOPPANA R, 1987, INFORMATION PROCESSI, V25, P27
[4]  
GOLDREICH O, 1991, J ACM, V38, P691, DOI 10.1145/116825.116852
[5]  
GOLDREICH O, 1986, P 27 IEEE S FOUND CO
[6]   THE KNOWLEDGE COMPLEXITY OF INTERACTIVE PROOF SYSTEMS [J].
GOLDWASSER, S ;
MICALI, S ;
RACKOFF, C .
SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :186-208
[7]  
Goldwasser S., 1985, P 17 ANN ACM S THEOR
[8]  
Goldwasser S., 1989, ADV COMPUTING RES, V5, P73
[9]   NEW GENERALIZATIONS OF REED-MULLER CODES .I. PRIMITIVE CODES [J].
KASAMI, T ;
LIN, S ;
PETERSON, WW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (02) :189-+
[10]  
Kolesnik V. D., 1968, Problems of Information Transmission, V4, P15