4
$\begingroup$
  1. Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)?

If $G_1$ is known to give minimum distance $d$ then the problem 'is the minimum distance with $G_2$ less than $d$?' is $NP$-complete.

  1. Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same number of minimum distance code words?' in $PP$ (I can see it in $P^{PP}$)?

If $G_1$ is known to give $N_d$ number of minimum distance $d$ then the problem 'is the number of minimum distance codewords with $G_2$ greater than $N_d$?' is $PP$-complete.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.