If A and B are NP-complete, then A ∪ B need not be NP-complete

Question

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\}\}^∗$

Answer 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.