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