1
$\begingroup$

I need some help with this question:

Definition: A Turing-machine that is a counter for the language $L$ is called 'polynomial counter' if there exists a polynomial $p$ s.t. every word $w\in L$ appears on the machine's tape starting from the $p(|w|)$ cell at most (that is, the first letter of $w$ is at cell $p(|w|)$ or before it).

Assuming that $P\neq NP$ prove/refute the following statement: If $L\in P$ then there exists a polynomial counter for $L$.

My intuition was to prove this due to the fact that we can arrange all words of $\Sigma^*$ in a lexical order and then in a polynomial time (since $L\in P$) check if $w \in L$. However, it is just a basic intuition.

Thank you

PS: it is worth mentioning that for a counting Turing Machine there is an output tape which is a write only tape and thus the words of L keeps accumulating on this tape one after the other.

$\endgroup$
2
  • $\begingroup$ Are two words allowed to "overlap"? $\endgroup$
    – nir shahar
    Jul 17, 2021 at 11:52
  • $\begingroup$ Although this doesn't answer your question, I added a clarification posted by OP in the comments of a previous answer of mine, now deleted. $\endgroup$
    – Steven
    Jul 17, 2021 at 12:11

2 Answers 2

1
$\begingroup$

Assuming words cant overlap, we will prove that the statement is false. Lets try to think about $\Sigma^*$ and see what happens (since as you said, it could be used to create a polynomial counter for all other languages in $P$).

Without loss of generality, we can assume that the polynomial counter will contain the words in increasing lexicographical ordering (why? try to prove this fact!)

So, let us take a look at a word $w$ with length $k=|w|$. We know that all words $w'\preceq w$ ($w'$ is lexicographically smaller than $w$) must come before $w$ on the tape. How many of them are there? at least $2^{k-1}$ such words exist (since $2^{k-1}$ is the number of words with length $k-1$). Even if all of those words were by any chance one letter long (which they aren't, they are $k-1$ letters long), that will still take up an entire $2^{k-1}$ cells. Therefore, $w$ can appear only after at least $2^{k-1}$ cells.

Clearly, $2^{k-1}$ is not polynomial in $k=|w|$, and hence there doesn't exist a polynomial counter for $\Sigma^*$

$\endgroup$
3
  • 1
    $\begingroup$ This is essentially the same argument as my answer. $\endgroup$
    – Steven
    Jul 17, 2021 at 12:19
  • 1
    $\begingroup$ @Steven yea, I wrote the answer and forgot to upload it -_- $\endgroup$
    – nir shahar
    Jul 17, 2021 at 12:39
  • 2
    $\begingroup$ @Steven although, my answer is more intuition-like, while your answer is a bit more rigorous. Its always good to have both sides! $\endgroup$
    – nir shahar
    Jul 17, 2021 at 14:03
1
$\begingroup$

The following assumes that words cannot overlap on the output tape.

Let $\Sigma=\{0,1\}$, pick $\Sigma^* \in \mathsf{P}$ as your language and suppose that there is a polynomial counter $T$ for $\Sigma^*$. Let $p(|w|) = |w|^{c_1} + c_2$ with $c_1, c_2 \ge 0$ be a polynomial for such that a word $w \in L$ starts in position at most $p(|w|)$ on the output tape of $T$.

Let $W= \langle w_1, w_2, \dots, \rangle$ be the list of the distinct words from $L$ that are written on the tape by $T$, in order.

For every $h = 0, 1, \dots$ let $L(h) = \sum_{i=1}^{h} |w_i|$. We must have: $$ p(|w_h|) \ge L(h-1). $$

Suppose that, for some indices $i <j$, we have $|w_i| > |w_j|$. Then by swapping $w_i$ and $w_j$ in $W$ we would still obtain a list $W'$ that satisfies the above property. Formally, let $w'_h = w_h$ if $h \not\in \{i, j\}$, $w'_i = w_j$, $w'_j = w_i$, and let $L'(h) = \sum_{i=1}^{h} |w'_i|$. For $h < i$ we have $L'(h)=L(h)$, for $h=i, \dots, j-1$ we have $L'(h) = L(h) - |w_i| + |w_j| < L(h)$, and for $h \ge j$ we have $L'(i)=L(i)$. Therefore, for $h \not\in {i,j}$: $$ p(|w'_h|) = p(|w_h|) \ge L(h-1) \ge L'(h-1). $$ Moreover, since $i<j$: $$ p(|w'_i|) = p(|w_j|) \ge L(j-1) \ge L'(j-1) \ge L'(i-1). $$ Finally: $$ p(|w'_j|) = p(|w_i|) \ge p(|w_j|) \ge L(j-1) \ge L'(j-1). $$

This allows us to assume, without loss of generality, that the words in $W$ appear in non-decreasing order of their length. Since $W$ must contains all words from $\Sigma^*$, the length of $w_h$ and the length of the $h$-th word from $\Sigma^*$ (in lexicographic order) must coincide.

Let $\ell > 2$ be a sufficiently large integer and define $k = 2^\ell$.

There are $2^0 + 2^1 + \dots + 2^{\ell-1} = 2^\ell - 1 = k-1$ words of length at most $\ell-1$ in $\Sigma^*$, and their total length is: $$ \sum_{i=0}^{\ell-1} i \cdot 2^i = \ell \cdot 2^\ell - 2 \cdot2^{\ell} + 2 > 2^{\ell}. $$

The length of the $k$-th word $w'$ in $\Sigma^*$ is $\ell$. Therefore we must have also $|w_k| = \ell$ and we can write: $$ \ell^{c_1} + c_2 = p(\ell) = p(|w_k|) \ge L(k-1) = \sum_{i=1}^{k-1} |w_i| = \sum_{i=0}^{\ell-1} i 2^i > 2^\ell. $$

By choosing a sufficiently large value of $\ell$ you get a contradiction.

$\endgroup$

Your Answer

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

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