Is the following language in P or NP?
EMPTY_TM = {⟨N⟩| N is a TM that accepts no input}
Can someone shed some light on how to come to such a conclusion also?
Asked
Active
Viewed 77 times
1
-
1Removed incorrect group-theory tag. A language must be decidable to be in P or NP in the first place. Also, P and NP are not mutually exclusive (nor exhaustive) options. – Erick Wong May 09 '13 at 20:39
-
Doesn't that language bear similarities to another language you've learned about? – May 09 '13 at 20:40
-
My guess is that it is not in P since you need to simulate each TM N on every string to verify that the language produced by N is empty?? – John May 09 '13 at 20:50
-
1EMPTY_TM is undecidable, therefore not in P – John May 09 '13 at 21:07
-
1You might want to look at Rice's Theorem – Rick Decker May 09 '13 at 23:53