# "Polynomial Counter" Turing Machine

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.

• Are two words allowed to "overlap"? Jul 17, 2021 at 11:52
• 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. Jul 17, 2021 at 12:11

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^*$$

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

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 , 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: $$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.