Register

Question on reducibility

1,175 views

1 Answer

Best answer
4 4 votes
2 can be TRUE. Both can be recursive as recursive set is a proper subset of r.e. set. But 1 can never be TRUE. So, given answer is correct. But does the "polynomial" word in question carry any significance?
• selected by
Voting & Accepting an answer helps improve the community
← Previous · can we find out mini...Next → · Question on graph th...
← Previous in category · can we find out mini...Next in category → · Equivalence of Turin...
Position:
Show:

Related questions

2 2 votes
1 1 answer
698
698 views
iarnav asked Sep 6, 2021
698 views
#TOC NPTEL ASSIGNMENT Question about reducibility
Please help me understand this question. I have searched on internet, but not avail. Click this to see the question
1 1 vote
1 1 answer
1.6k
1.6k views
sunaina rawat asked Oct 2, 2017
1,575 views
Reducibility
Why this is incorrect? For any two languages A and B, if A ⊆ B, then A is reducible to B.
0 0 votes
0 0 answers
1.4k
1.4k views
srestha asked Sep 12, 2018
1,446 views
Reducibility
State which are TRUE and which are FALSE (Question 1) and 2) both have same options)$1)$If there is an algorithm for polynomial time reduction from A to B?$2)$ if there i...
0 0 votes
0 0 answers
446
446 views
HeadShot asked Dec 4, 2018
446 views
Doubt : Reducibility
$Question:$ https://gateoverflow.in/63261/%23made-easy $Approach:$ A is reduced to B . Here reduction is done at polynomial time.Here B is solved in polynomial time. S...