3.4. Bài toán phổ trọng số của mã tuyến tính

Định nghĩa 3.33 (Bài toán phổ trọng số)

Bài toán về phổ trọng số của mã tuyến tính \(WS(\bm{H}, t)\) là bài toán nhận dạng trong code, với ma trận parity-check \(\bm{H}\), có tồn tại hay không vector \(\bm{c} \in V_n(q)\) có trọng số Hamming bằng \(t\) và thỏa mãn \(\bm{H} \bm{c}^\top = \bm{0}\).

Định lý 3.1 (Định lí từ [12])

Bài toán về phổ trọng số là NP-complete.