1
$\begingroup$

I have the language

$\{ w \mid w \text{ contains an equal amount of symbols } a \text{ and } b\}$.

I want to show that the language is in the class $\textsf{P}$. To do this, I must give an implementation level description of the relevant Turing machine. I'm not very knowledgeable on Turing machines, but I think I would be able to write down a possible transition function, but from this how do I compute the complexity, in order to show it is in the class $\textsf{P}$?

$\endgroup$
1
$\begingroup$

You only have to show that there exists a Turing machine that decides the language, and such that the number of steps taken by it is a polynomial in the size of the input, in this case a polynomial in $|w|$.

An example of such a machine is the following. Scan the tape left to right until you find both an $a$ and a $b$, and replace both of them with a new symbol, let's say $x$. If you fail to find both an $a$ and a $b$, there are two cases: if every nonblank symbol on the tape is $x$, answer $\textsf{YES}$, otherwise answer $\textsf{NO}$.

It should be easy to see that the number of steps is $O(|w|^2)$, and therefore the language is in $\textsf{P}$.

Just a pedantic note: we usually talk about the complexity of languages or problems, not machines. It would be more appropriate to say "number of steps taken" or "amount of space used" rather than "time complexity" or "space complexity" when talking about a specific Turing machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy