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

Định nghĩa 2.69

Bài toán về phổ trọng số của linear code (hay Задача о спектре весов линейного кода) \(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í 2.7 (Định lí từ [35])

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