Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following seems to me like a natural definition and I wonder whether it's been studied somewhere

Consider $\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}$ a set of languages. Then $K \subset \lbrace 0, 1 \rbrace^\omega$ is called "$\mathsf{X}$-verifiable information" when there is $L \in \mathsf{X}$ s.t.

(i) Given $x \in L$, every prefix of $x$ is in $L$

(ii) Given $f \in K$, every prefix of $f$ is in $L$

(iii) Given $f \notin K$, the length $n$ prefix of $f$ is outside $L$ for $n >> 0$

For example $\lbrace f \rbrace$ is $\mathsf{R}$-verifiable information iff $f$ is computable. This can be seen by constructing an algorithm which runs the verification on all strings of length $n$ and collects the prefixes of length $m$ of those strings which passed the verification. For $n >> m$, the only prefix which remains is the correct one

However if $K$ is $\mathsf{R}$-verifiable information it doesn't mean every $f \in K$ is computable: for example consider $K = \lbrace 0, 1 \rbrace^\omega$

A non-trivial example of $\lbrace f \rbrace$ which is $\mathsf{P}$-verifiable is as follows. Consider $L \in \mathsf{NP} \cap \mathsf{coNP}$ and let $f$ be an encoding of $L$ together with the corresponding $\mathsf{NP}$ and $\mathsf{coNP}$ witnesses (i.e. for each $x \in \lbrace 0, 1 \rbrace^*$, $f$ encodes either an $\mathsf{NP}$-witness proving $x \in L$ or a $\mathsf{coNP}$-witness proving $x \notin L$)

share|cite|improve this question
When you write "$\lbrace f \rbrace$ is $\mathsf{R}$-verifiable information iff $f$ is computable", I don't understand exactly what is $\lbrace \cdot \rbrace$ and what is $\mathsf{R}$. – a3nm Dec 29 '12 at 9:27
@a3nm : {f} is the set with one element f. R is the set of recursive languages – Squark Dec 29 '12 at 11:37
Your question seems to be a reformulation of an error correcting code problem (Golay code, Hamming code) but in terms of prefixes... Perhaps this may be a good start in the background literature for you? – Phil Jul 25 '13 at 4:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.