<p><span class="math-container">$K\subseteq\{0,1\}^\omega$</span> is <span class="math-container">$\mathsf{R}$</span>-verifiable if and only if <span class="math-container">$K$</span> is a <a href="https://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_subsets_of_Cantor_and_Baire_space" rel="nofollow noreferrer"><span class="math-container">$\Pi^0_1$</span> class</a> (in Cantor space), a concept that has been studied extensively in <a href="/questions/tagged/computability-theory" class="post-tag" title="show questions tagged &#39;computability-theory&#39;" rel="tag">computability-theory</a>. They are also called effectively closed sets.</p>

<p>A set <span class="math-container">$K$</span> is a <span class="math-container">$\Pi^0_1$</span> class iff it is the set of infinite paths through a recursive (computable) tree, and this is the version of the concept that you defined.</p>

<p>A monograph devoted to them:</p>

<p><a href="https://people.clas.ufl.edu/cenzer/publications/" rel="nofollow noreferrer">Effectively Closed Sets</a> (Douglas Cenzer and Jeffrey B. Remmel), Perspectives in Logic, Cambridge U. Press, 350 pages, to appear.</p>

CC BY-SA 4.0
2018-09-23T06:58:50.150Z
2018-09-23T06:58:50.150Z
Bjørn Kjos-Hanssen
<p>The following seems to me like a natural definition and I wonder whether it's been studied somewhere</p>

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

<p>(i) Given $x \in L$, every prefix of $x$ is in $L$</p>

<p>(ii) Given $f \in K$, every prefix of $f$ is in $L$</p>

<p>(iii) Given $f \notin K$, the length $n$ prefix of $f$ is outside $L$ for $n &gt;&gt; 0$</p>

<p>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 &gt;&gt; m$, the only prefix which remains is the correct one</p>

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

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

CC BY-SA 3.0
2012-12-29T09:27:22.573Z
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}$.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-12-29T11:37:17.083Z
@a3nm : {f} is the set with one element f. R is the set of recursive languages
Vanessa
CC BY-SA 3.0
2013-07-25T04:21:06.843Z
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
<cc.complexity-theory><reference-request>
"Verifiable information": is this a known concept?
Vanessa
# "Verifiable information": is this a known concept?

(Asked by: username_0 on 2012-12-28)

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

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: 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}$.  
> **username_0**: @a3nm : {f} is the set with one element f. R is the set of recursive languages  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_3 on 2018-09-23. Score: 4

$K\subseteq\{0,1\}^\omega$ is $\mathsf{R}$-verifiable if and only if $K$ is a [$\Pi^0\_1$ class](https://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_subsets_of_Cantor_and_Baire_space) (in Cantor space), a concept that has been studied extensively in [computability-theory](/questions/tagged/computability-theory "show questions tagged 'computability-theory'"). They are also called effectively closed sets.

A set $K$ is a $\Pi^0\_1$ class iff it is the set of infinite paths through a recursive (computable) tree, and this is the version of the concept that you defined.

A monograph devoted to them:

[Effectively Closed Sets](https://people.clas.ufl.edu/cenzer/publications/) (Douglas Cenzer and Jeffrey B. Remmel), Perspectives in Logic, Cambridge U. Press, 350 pages, to appear.


---

