Consider the following decision problem, which we will call COMPARE. We are given as input a pair $(V_0, V_1)$ of linear codes in $\mathbb{F}_2^n$, and asked to decide whether $V_0, V_1$ have the same weight enumerator polynomial. Recall that, for a linear code $V\subseteq\mathbb{F}_2^n$, the weight enumerator polynomial of $V$ is $$\textrm{wt}_V(x):=\sum_{j=0}^na_jx^j$$ where $a_j:=\#\{v\in V: |v|=j\}$. Do we know anything about the hardness of this problem? For some additional background, recall that $V_0, V_1$ are said to be equivalent if there is a permutation of the $n$ coordinate bits that carries $V_0$ to $V_1$. A result of Petrank and Roth is that:
a) deciding whether two codes are equivalent is (probably) not too hard, in the sense that this problem is not NP-complete, unless the polynomial hierarchy collapses, but
b) on the other hand, deciding code equivalence is at least as hard as GRAPH ISOMORPHISM
If two codes are equivalent, they have the same weight enumerator polynomial. The converse, however, is not true. I suspect that deciding whether $\textrm{wt}_{V_0}(x)=\textrm{wt}_{V1}(x)$ is NP-hard, but can't find anything in the literature about the status of this problem. On the other hand, the following are all well-known:
The functional problem of computing the coefficients of $\textrm{wt}_V(x)$ is #P-hard.
It is NP-hard to decide, given an integer $w>0$, whether there is a $0<k\leq w$ with $a_k\neq 0$ (Vardy)
For $n$ even, the problem of deciding whether $a_{n/2}=0$ is NP-hard (Calderbank and Shor)
I also suspect that COMPARE does not even lie in NP (unlike code equivalence, there doesn't seem to be a poly-sized certificate of a yes-instance). However, it seems extremely difficult to prove that COMPARE is NP-hard. Consider the analogous situation with the chromatic polynomial. As far as I know, it is wide open to prove the NP-hardness of deciding, on input a pair of graphs $(G, G')$, whether $G$ and $G'$ have the same chromatic polynomial, so the original question above might be too ambitious. I have two easier follow-up questions:
Q1) is COMPARE at least as hard as hard as code equivalence and thus at least as hard as GRAPH ISOMORPHISM? In other words, if I give you two codes with the promise that they have the same weight distribution, could you decide in polynomial time whether they are equivalent?
Q2) Given a paramater $\alpha\in\mathbb{C}$, we define decision problem COMPARE($\alpha)$ as follows: On input a pair of binary linear codes $V_0, V_1$, decide whether $\textrm{wt}_{V_0}(\alpha)=\textrm{wt}_{V_1}(\alpha)$. Are there any $\alpha\in\mathbb{C}$ for which COMPARE$(\alpha)$ is NP-hard? Note that, if $|\alpha|\neq 0,1$, then COMPARE($\alpha)$ is at least as hard as COMPARE, so it should be easier to prove that there exists an $\alpha\in\mathbb{C}$ for which COMPARE($\alpha)$ is NP-hard. In fact, I suspect that it should be much easier to prove this. Returning to the graph coloring analogy, even though we have no idea whether it is hard to decide whether two input graphs $G,G'$ have the same chromatic polynomial, we do know that, for any integer $k>2$, it is NP-hard to decide whether $P(G, k)=P(G', k)$.
It's also worthy of note that COMPARE is indeed NP-hard over $\textrm{GF}(2^m)$, because then it is NP-hard to decide if a code is an MDS code (Vardy), and there exists precisely one weight distribution, depending on $n,k,2^m$, such that a linear code over $\textrm{GF}(2^m)$ is MDS if and only if it has that weight distribution. Unfortunately, that does not work for $m=1$.
