272 views

1 Answer

0 votes
0 votes
S1: False

Ex  A=[0,1)  (set of all real no. between 0 and 1)

     B=N  (Set of all natural numbers)

here A∩B is an empty set which is finite

S2:False

Because a hard problem can be a subset of an easy problem and not reducible to easy problem

Ex A=$A_{TM}$  (Turing recognizable but not decidable language i.e. Recursive Enumerable languages)   

B=$ \sum^*$  

B is decidadle
A  is a subset of B
but A is not reducible to B

No related questions found