<p>An answer to the first question can be found in a paper by Schaefer and Umans, <a href="http://www.hni.uni-paderborn.de/fileadmin/Fachgruppen/Algorithmen/Lehre/Vorlesungsarchiv/WS_2011_12/Komplexitaetstheorie/phcom.pdf" rel="nofollow">Completeness in the polynomial-time hierarchy: A compendium</a> (2002).</p>

<p>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).</p>

<p>I guess following the references should help in digging out more related problems.</p>

CC BY-SA 3.0
2014-02-28T13:11:06.450Z
Good reference.
Turbo
CC BY-SA 3.0
2014-02-28T10:18:37.370Z
2014-02-28T10:18:37.370Z
dd1
<p>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.</p>

<p>My questions are the following:</p>

<p>$(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?</p>

<p>$(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 <a href="http://www.math.ias.edu/~ormeir/papers/ip_pspace.pdf" rel="nofollow">http://www.math.ias.edu/~ormeir/papers/ip_pspace.pdf</a>)</p>

<cc.complexity-theory><complexity-classes><coding-theory><polynomial-hierarchy><pspace>
Coding theory and complete problems
Turbo
# Coding theory and complete problems

(Asked by: username_0 on 2014-02-26)

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>)

**Tags:** cc.complexity-theory, complexity-classes, coding-theory, polynomial-hierarchy, pspace


---

## 1 answers

### Answer by username_1 on 2014-02-28. Score: 3 | Accepted answer

An answer to the first question can be found in a paper by Schaefer and Umans, [Completeness in the polynomial-time hierarchy: A compendium](http://www.hni.uni-paderborn.de/fileadmin/Fachgruppen/Algorithmen/Lehre/Vorlesungsarchiv/WS_2011_12/Komplexitaetstheorie/phcom.pdf) (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.

> **Comments:**
> **username_0**: Good reference.  

---

