Gate Exam

Consider three decision problems P1,P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
option
(a) P3 is decidable if P is reducible to P3
(b) P3 is undecidable 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

Read Solution (Total 0)

Gate Other Question
What is the minimum number of ordered pairs of non-negative numbers that should be
chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that ac mod
3andbd mod 5
(a) 4
(b) 6
(c) 16
(d) 24 Consider the set H of all 3 x 3 matrices of the type
a f e
O b d
O O c
where a,b,c,d,e and f are real numbers and abcO. under the matrix
multiplication operation, the set H is:
option
(a) a group
(b) a monoid but not a group
(c) a semi group but not a monoid
(d) neither a group nor a semi group