992 views
1 votes
1 votes
Why this is incorrect?
 For any two languages A and B, if A ⊆ B, then A is reducible to B.

1 Answer

4 votes
4 votes

let suppose A ⊆ B means A is reducible to B .

we know every language is subset of ∑* , which is regular

so every language in this world is reducible to regular language , so ultimately every language would become decidable in that way. Undecidability gone...

A ⊆ B  only means A is subset of B , nothing else...

A ⊆p B means A is poly time reducible to B , means if A is undecidable then B will too...

Related questions

2 votes
2 votes
1 answer
1
iarnav asked Sep 6, 2021
449 views
Please help me understand this question. I have searched on internet, but not avail. Click this to see the question
2 votes
2 votes
1 answer
2
shikharV asked Jan 4, 2016
811 views
Please check if the given answer is correct or not.