A Exam related question plz help

From: navzit@xxxxxxxxx
Date: 15 Jan 2007 19:57:41 -0800

i am appearing for my post grad exam which has got the following
question

Given three decison problem P1 P2 and P3 ,such that P1 is decidable and
P2 is undecidable .Then which of the option is true:

(a) P3 is decidable if P1 is reducible to P3.
(b) P3 is decidable if P3 is reducible to P2.
(c)P3 is undecidable if P2 is reducible to P3
(d) P3 is decidable if P3 is reducible to P2's complement.

Another one given postorder and preorder traversal of a binary tree can
one draw the tree?
Thanks

.

Follow-Ups:
- Re: A Exam related question plz help
  - From: Chris Smith

Prev by Date: Re: trying to use the pumping lemma
Next by Date: Re: question on proving a language is regular
Previous by thread: trying to use the pumping lemma
Next by thread: Re: A Exam related question plz help
Index(es):
- Date
- Thread