# P2928: Complexity of equality for binary-code weight enumerators - ID: `P2928` - Reference: `binary-code-weight-enumerator-equality-complexity` - Page: https://theoremdb.org/statements/P2928 - Record maturity: Reviewed problem with recorded work ## Problem Given generator matrices for two binary linear codes of the same block length, what is the computational complexity of deciding whether their weight enumerator polynomials are equal? In particular, is this decision problem NP-hard under deterministic polynomial-time many-one reductions? ### Problem setup - **Remark.** For a binary linear code C subset of {0,1}^n, its weight enumerator is W_C(x)=sum_{c in C} x^{wt(c)}, where wt(c) is Hamming weight. - **Definition.** The input consists of two binary matrices whose row spans define the codes; redundant rows are allowed and the common block length is part of the input. ### What counts as a solution - Give a deterministic polynomial-time algorithm with proof, or prove hardness under a named standard reduction and place the problem in the strongest justified upper complexity class. - A hardness proof must map every input to two explicitly constructible binary generator matrices and prove equality of their entire weight enumerators exactly when the source instance is a yes-instance. ## Status Unresolved in this packet after the dated source check. Strongest checked result: Evaluating weight enumerators and finding minimum distance have strong hardness results, while the recent MathOverflow thread gives no reduction or algorithm for equality of the full polynomials. Exact unresolved remainder: Give a deterministic polynomial-time algorithm with proof, or prove hardness under a named standard reduction and place the problem in the strongest justified upper complexity class. A hardness proof must map every input to two explicitly constructible binary generator matrices and prove equality of their entire weight enumerators exactly when the source instance is a yes-instance. [2](#reference-2) [3](#reference-3) [1](#reference-1) ## Work ### Evidence for the current status **Claim 1 (Dated status and exact unresolved remainder).** Unresolved in this packet after the dated source check. Strongest checked result: Evaluating weight enumerators and finding minimum distance have strong hardness results, while the recent MathOverflow thread gives no reduction or algorithm for equality of the full polynomials. Exact unresolved remainder: Give a deterministic polynomial-time algorithm with proof, or prove hardness under a named standard reduction and place the problem in the strongest justified upper complexity class. A hardness proof must map every input to two explicitly constructible binary generator matrices and prove equality of their entire weight enumerators exactly when the source instance is a yes-instance. The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: Evaluating weight enumerators and finding minimum distance have strong hardness results, while the recent MathOverflow thread gives no reduction or algorithm for equality of the full polynomials. Exact unresolved remainder: Give a deterministic polynomial-time algorithm with proof, or prove hardness under a named standard reduction and place the problem in the strongest justified upper complexity class. A hardness proof must map every input to two explicitly constructible binary generator matrices and prove equality of their entire weight enumerators exactly when the source instance is a yes-instance. ### Background and intake notes Puncturing and shortening identities, direct-sum gadgets, and coefficient-isolation reductions can be reused. The comparison problem may behave differently from computing one enumerator, so a direct reduction is required. - Original intake status: UNKNOWN as of 2026-07-27. Evaluating weight enumerators and finding minimum distance have strong hardness results, while the recent MathOverflow thread gives no reduction or algorithm for equality of the full polynomials. - The MathOverflow page and every visible answer and comment were checked on 2026-07-27. The page has no accepted resolution of the equality problem. - Vyalyi's arXiv:cs/0304044 was checked for the complexity of evaluating weight enumerators. Evaluation hardness does not automatically imply hardness of comparing two succinctly represented polynomials. - Vardy's minimum-distance hardness theorem was checked as a possible reduction source. The audit did not locate a published gadget converting minimum distance or a coefficient query into equality of two complete enumerators. - A local corpus search for code weight enumerator equality, polynomial identity, and binary generator matrix found no duplicate. - Recorded example: Row-reducing a generator matrix removes redundant generators without changing the code or its weight enumerator, giving a polynomial-time normalization step. ### Open directions - **Route 1** (reported): Give a deterministic polynomial-time algorithm with proof, or prove hardness under a named standard reduction and place the problem in the strongest justified upper complexity class. A hardness proof must map every input to two explicitly constructible binary generator matrices and prove equality of their entire weight enumerators exactly when the source instance is a yes-instance. [1](#reference-1) ### Working on this Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `binary-code-weight-enumerator-equality-complexity`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome. ## References 1. MathOverflow question 498913, “Complexity of equality for binary-code weight enumerators,” checked 2026-08-01. Question 498913 and every visible answer and comment were checked on 2026-07-27. https://mathoverflow.net/questions/498913/is-it-hard-to-decide-if-two-codes-have-the-same-weight-enumerator-polynomial - Also cited at Full question, answers, and visible comments concerning Complexity of equality for binary-code weight enumerators; checked 2026-08-01. - Also cited at Editorial research route recorded 2026-08-01. - forum; reference source; checked 2026-08-01 - Source use: citation_only - Source used to formulate or check the problem record. - Source used to assess the problem's recorded status. - For Complexity of equality for binary-code weight enumerators, the reviewed source scope is Full question, answers, and visible comments concerning Complexity of equality for binary-code weight enumerators; checked 2026-08-01.. The packet makes no inference beyond that cited scope. - Source named by the research packet. 2. M. N. Vyalyi, “Hardness of approximating the weight enumerator of a binary linear code,” arXiv:cs/0304044 (2003). abstract and main hardness results for exact and additive-approximate evaluation of a binary-code weight enumerator https://arxiv.org/abs/cs/0304044 - preprint; reference source; arXiv:cs/0304044, checked 2026-08-01; checked 2026-08-01 - Source use: citation_only - Source used to assess the problem's recorded status. - For Complexity of equality for binary-code weight enumerators, this source establishes hardness for evaluating one enumerator, rather than deciding equality of two complete enumerator polynomials. 3. A. Vardy, “The intractability of computing the minimum distance of a code,” IEEE Transactions on Information Theory 43(6) (1997), 1757-1766. DOI 10.1109/18.641542. main theorem on NP-hardness of computing a binary linear code's minimum distance https://doi.org/10.1109/18.641542 - scholarly_publication; reference source; checked 2026-08-01 - Source use: citation_only - Source used to assess the problem's recorded status. - For Complexity of equality for binary-code weight enumerators, this source was excluded as status evidence because minimum-distance hardness does not imply hardness of weight-enumerator equality; it is retained to document source-review history.