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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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