One Stop GATE Forum: gate 2003 question

Message

   Nobody knows yet if P=NP. Let

L= (0+1)*               if P=NP

  = fi(empty set)      otherwise.

which of the following statement is true.

a.      L is recursive

b.      L is recursively enumarable but not recursive.

c.       L is not recursively enumarable.

d.      Whether L is recursive or not will be known after we find out if P=NP

Author	Message
Adhiti Newbie Joined: 02Feb2007 Online Status: Offline Posts: 32	Topic: gate 2003 question Posted: 02Feb2007 at 11:55am
	Nobody knows yet if P=NP. Let L= (0+1)* if P=NP = fi(empty set) otherwise. which of the following statement is true. a. L is recursive b. L is recursively enumarable but not recursive. c. L is not recursively enumarable. d. Whether L is recursive or not will be known after we find out if P=NP Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged

Alok Newbie Joined: 02Feb2007 Online Status: Offline Posts: 19	Posted: 02Feb2007 at 4:34pm
	(0+1)* and epsilon(empty string) both are regular lang. that means both are recursive. whether P=NP or not L will always be recursive!! ans is (A).
	IP Logged


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers