Symmetric
如何計算線性映射的分支數？
是否有一種有效的算法可用於確定任何給定線性映射的分支數？
正如問題的答案中所解釋的那樣，線性 映射的分支號 $$ A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x $$ 是矩陣生成的線性碼的最小權重 $$ G=[~I~|~A]. $$ 對於任意矩陣 $ A $ 這個問題是NP難的，即非常難。對於像 AES 中的 MDS 矩陣這樣的結構化矩陣，答案是已知的，請參見連結。
有關硬度結果，請參閱 Vardy 的論文“計算程式碼最小距離的難處理性”。它或相關版本也可以在 citeseer 上找到。由於此程式碼是線性最小距離等於最小權重。