If A and B are NP-complete, then A ∪ B need not be NP-complete I am studying the proof of this exercise (link)


  There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example:
  
  $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$
  $B = \{0x : x ∈ SAT\} ∪ \{1x : x ∈ \{0, 1\}^∗\};$.
  
  The languages A and B are N P-complete (prove it). On the other hand, A ∪ B contains allbinary strings (i.e. A ∪ B = {0, 1}∗); and thus it is not N P-complete.


I know the Union (L1 ∪ L2) of two NP language L1,L2 ∈ NP is NP. I can describe a TM not-deterministic for $\{1x : x ∈ SAT\}$ (and for $\{0x : x ∈ SAT\}$) and therefore $\{1x : x ∈ SAT\}$ is NP (note, I know SAT is NP). I have a problem to understand why $\{0x : x ∈ \{0, 1\}\}^∗$ is NP? I remember $\{0, 1\}^∗$ is in P, and I cannot describe a TM not-deterministic for $\{0x : x ∈ \{0, 1\}\}^∗$
P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.