0 votes 0 votes If a problem A is reducable to problem B and it is known that B is undecidable then is A undecidable? Theory of Computation theory-of-computation + – Rajesh R asked Dec 20, 2017 Rajesh R 301 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Ashwin Kulkarni commented Dec 20, 2017 reply Follow Share It is false. I mean A may or may not be undecidable. 0 votes 0 votes saxena0612 commented Dec 20, 2017 reply Follow Share It only implies that A is equal or less hard as compared to B but inferring anything apart from this is not true. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes The answer is True because if we reduce the instance of the problem of class A into class B in polynomial time then A and B belong to same class. Raj Kumar 7 answered Dec 23, 2017 Raj Kumar 7 comment Share Follow See all 0 reply Please log in or register to add a comment.