Why is $\mathbf{P}/\mathbf{1}$ uncountable?

47 Views Asked by At

Define $\mathbf{P}/k(n)$ to be the class of languages $L \subseteq {0, 1}^*$ such that there is a polynomial-time Turing machine $M(x,y)$, and a collection ${a_n}_{n\in\mathbf{N}}$ of binary strings, with $\vert a_n \vert = k(n)$, such that for all $x$, $M(x, a_{\vert x \vert}) = 1$ iff. $x\in L$.

Why is $\mathbf{P}/1$ uncountable?

1

There are 1 best solutions below

0
On

Given $A\subset \Bbb N$, we can define the language $$L_A:=\{\,x\in\{0,1\}^*:|x|\in A\,\}.$$ Since there are uncountably many such sets $A$, there are uncountably many such languages. Each of these languages is in $\mathbf{P}/1$. To see this, just let $$a_n=\begin{cases}1&n\in A\\0&n\notin A\end{cases}$$ and let $M(x,y)$ be the Turing machine that maps $(x,y)\mapsto y$ (obviously works in polynomial time). Clearly, we have $$M(x,a_{|x|})=1\iff x\in L_A.$$