7
$\begingroup$

Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete.

My questions are the following:

$(1)$ Are there natural good examples of coding theory problems that lie in different levels of the polynomial hierarchy above NP and are complete for those levels?

$(2)$ Are there natural good examples of coding theory problems that are PSPACE complete? (Note that a coding theory approach is used to show IP=PSPACE in http://www.math.ias.edu/~ormeir/papers/ip_pspace.pdf)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).

In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($r$ part of the input). A certain $\Sigma_3^p$-complete problem called "Minimum block decoder" can be found on p. 28 (see also $\Sigma_2^p$-complete "Minimal block encoder and decoder", p. 25).

I guess following the references should help in digging out more related problems.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good reference. $\endgroup$
    – Turbo
    Feb 28, 2014 at 13:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.