I have the following question about complexity time classes. Given the language $L = \{0,1\}^*$, is it inside the class P or not?

$$ L = \{0,1\}^∗ ∈ P? $$

  • $\begingroup$ What's your guess? Do you see an algorithm to test whether $w \in L$? $\endgroup$ – holf Oct 15 '19 at 12:04
  • $\begingroup$ Your language is regular and so can be decided in linear time. $\endgroup$ – Yuval Filmus Oct 15 '19 at 12:35

A useful exercise to answer the question could be to build a simple Turing machine $M$ (let's say one tape and one head) that recognizes your language. Such a TM could work directly on the input tape and be equipped with an extremely simple transition function:

  1. Read input

  2. If $($input $= 0$ $\lor$ input $= 1$$)$ $\implies$ Move R (right on the tape)

Note that this machine can be "read-only" it doesn't need to write anything. Suppose that the input tape is encoded like this:

$I = [\varnothing, 0, 1,1,0,0,1,0,0,1,0,0,1,1,.........,\varnothing]$ and that your TM start from the left blank symbol and HALT $\iff$ it reaches the final blank symbol, you can notice that this machine HALT $\iff$ it recognizes $L$.

I strongly suggest you do this exercise, writing down the formal definition of the machine, especially the transition function's table. Once this is done it will be much easier for you to answer these questions:

  1. What is the time complexity of running $M$ on $w$ $\in$ $L$ if |$w$| $=n$ ?
  2. Is $w$ $\in$ $L$ regular and why?

Your Answer

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

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